【BZOJ 2851】极限满月

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2851
数据生成器:http://paste.ubuntu.com/23321973/

这道题我真的是服了。 服气!
0_7uftv1i06u7jhr9

如果考虑{ai}为父亲集合的话
这货是个DAG
然后看一看{bi}中涉及到的∩操作
从顶端向下考虑的话,这™不就是支配点!
于是求一求灾难树,然后求一求路径并

话说这么巧妙的题目出题人是怎么想到的!
服! 真心服!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = N*200;

int head[N],nxt[M],to[M],n,m,in[N],out[N];
int que[N],fa[N][18],dep[N],num_cnt;
vector<int> G[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0; in[v]++;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline bool cmp(const int &a, const int &b) {
	return in[a] < in[b];
}

inline int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}	
	if (x == y) return y;
	for (int i=17;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

inline void solve(int w) {
	dep[w] = dep[fa[w][0]] + 1;
	if (w) G[fa[w][0]].push_back(w);
	for (int i=1;i<=17;i++) {
		fa[w][i] = fa[fa[w][i-1]][i-1];
	}
	
	for (int i=head[w];i;i=nxt[i]) {
		if (!~fa[to[i]][0]) {
			fa[to[i]][0] = w;
		} else {
			fa[to[i]][0] = lca(fa[to[i]][0], w);
		}
		
		if (!--in[to[i]]) solve(to[i]);
	}
}

void DFS(int w) {
	in[w] = ++num_cnt;
	for (int i=G[w].size()-1;~i;i--) {
		DFS(G[w][i]);
	}
	out[w] = num_cnt;
}

int main(){
	memset(fa,-1,sizeof(fa));
	n = read();
	for (int i=1;i<=n;i++) {
		for (int j=read();j;j--) {
			Add_Edge(read(),i);
		}
		if (!in[i]) {
			Add_Edge(0,i);
		}
	}
	
	fa[0][0] = 0;
	solve(0);
	DFS(0);
	
	m = read(); 
	for (int k=1,len,vout=0;k<=m;k++,vout=0) {
		len = read();
		for (int j=1;j<=len;j++) {
			que[j] = read();
		}
		
		sort(que+1,que+1+len,cmp);
		for (int i=1,pre=0;i<=len;i++) {
			vout += dep[que[i]];
			vout -= dep[lca(pre,que[i])];
			pre = que[i];
		}
		
		printf("%d\n",vout);
	}
	return 0;
}

—– UPD 2016.10.16 —–
今天发现这题数据范围有问题
关系数应该是小于2e6
点数应该是小于2e5

21 thoughts to “【BZOJ 2851】极限满月”

  1. Hi there! Someone in my Myspace group shared this site with us so I came to take a
    look. I’m definitely loving the information. I’m
    bookmarking and will be tweeting this to my followers! Great blog and brilliant design.

  2. Have you ever thought about writing an e-book or guest authoring on other websites?
    I have a blog based on the same ideas you discuss and would love to have you share
    some stories/information. I know my visitors
    would enjoy your work. If you’re even remotely interested, feel free to
    shoot me an email.

  3. I would like to thank you for the efforts you have put in writing
    this site. I really hope to view the same high-grade content by
    you later on as well. In fact, your creative writing abilities has inspired me to get my own, personal blog now 😉

  4. Write more, thats all I have to say. Literally, it
    seems as though you relied on the video to make your point.
    You clearly know what youre talking about, why throw away your
    intelligence on just posting videos to your blog when you could be
    giving us something enlightening to read?

  5. Your style is unique in comparison to other folks I’ve read
    stuff from. I appreciate you for posting when you’ve got the opportunity,
    Guess I’ll just bookmark this page.

  6. At this time it sounds like Movable Type is the preferred blogging platform out there right now.
    (from what I’ve read) Is that what you are using on your blog?

  7. Definitely believe that which you stated. Your favorite reason appeared to be on the web the simplest thing to be aware of. I say to you, I certainly get irked while people consider worries that they just don’t know about. You managed to hit the nail upon the top and also defined out the whole thing without having side effect , people could take a signal. Will likely be back to get more. Thanks

  8. Nice blog here! Also your web site loads up fast!
    What web host are you using? Can I get your affiliate link to your host?
    I wish my web site loaded up as fast as yours
    lol

  9. I am really impressed with your writing skills as
    well as with the layout on your blog. Is this a paid theme
    or did you modify it yourself? Anyway keep up the excellent
    quality writing, it’s rare to see a nice blog like this
    one today.

  10. Very good blog! Do you have any tips for aspiring writers?
    I’m planning to start my own site soon but I’m a little lost on everything.
    Would you advise starting with a free platform like WordPress or go for a paid option? There are so many choices out there that I’m completely confused ..
    Any suggestions? Thanks a lot!

  11. hello!,I love your writing so a lot! percentage we communicate more about your article on AOL?
    I need a specialist in this area to unravel my problem.
    Maybe that’s you! Having a look ahead to see you.

  12. I know this web site gives quality depending content and other data,
    is there any other web site which gives these kinds of information in quality?

  13. hello!,I like your writing very much! share we communicate more about your article on AOL? I need an expert on this area to solve my problem. Maybe that’s you! Looking forward to see you.

Leave a Reply to oprolevorter Cancel reply

Your email address will not be published. Required fields are marked *