题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3572
数据生成器:http://paste.ubuntu.com/23376760/
一看数据范围肯定知道是虚树辣!
题解的话,让我们召唤曹清华:http://blog.csdn.net/jzhang1/article/details/50630194
然后就是恶心的码代码环节…..
人太懒,于是带了两个log,慢成翔 qwq
#include<bits/stdc++.h> #define LL long long #define abs(x) ((x)<0?-(x):(x)) using namespace std; const int N = 300000+9; const int M = N << 1; const int INF = 1000000000; int head[N],nxt[M],to[M],T,n,m,tot,num[N],blg[N],p[N],sz[N]; int stk[N],top,dep[N],fa[N][18],size[N],vis[N],vout[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 AddEdge(int u, int v) {to[++T] = v; nxt[T] = head[u]; head[u] = T;} inline void Add_Edge(int u, int v) {AddEdge(u,v);AddEdge(v,u);} inline bool CMP(int a, int b) {return num[a] < num[b];} void DFS(int w, int f) { static int dfs_cnt = 0; num[w] = ++dfs_cnt; fa[w][0] = f; dep[w] = dep[f]+1; size[w] = 1; 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 (to[i] != f) { DFS(to[i], w); size[w] += size[to[i]]; } } } 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 x; 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 int dis(int x, int y) { int lca = LCA(x, y); return dep[x] + dep[y] - dep[lca]*2; } inline void Build(int root) { p[++tot] = root; stk[top=1] = root; sz[root] = n; for (int i=1,w,lca;i<=m;i++) { w = p[i]; lca = LCA(stk[top],w); while (dep[stk[top]] > dep[lca]) { if (dep[stk[top-1]] < dep[lca]) AddEdge(lca, stk[top]); else AddEdge(stk[top-1], stk[top]); top--; } if (lca != stk[top]) { stk[++top] = lca; p[++tot] = lca; sz[lca] = size[lca] - 1; } if (w != stk[top]) { stk[++top] = w; sz[w] = size[w] - 1; } } for (int i=1;i<top;i++) AddEdge(stk[i], stk[i+1]); } void prework_1(int w, int up) { blg[w] = vis[w]?w:up; for (int i=head[w];i;i=nxt[i]) { prework_1(to[i], vis[w]?w:up); if (~blg[to[i]]) { int len1 = (~blg[w]?abs(dep[blg[w]] - dep[w]):INF); int len2 = abs(dep[blg[to[i]]] - dep[w]); if (!~blg[w] || len1 > len2 || (len1 == len2 && blg[to[i]] < blg[w])) blg[w] = blg[to[i]]; } } } void prework_2(int w) { for (int i=head[w];i;i=nxt[i]) { if (blg[w] != blg[to[i]]) { int len1 = dis(blg[w], to[i]); int len2 = dis(blg[to[i]], to[i]); if (len1 < len2 || (len1 == len2 && blg[w] < blg[to[i]])) blg[to[i]] = blg[w]; } prework_2(to[i]); } } void solve(int w) { for (int i=head[w],len,cur;i;i=nxt[i]) { top = to[i]; for (int j=17;~j;j--) { if (dep[fa[top][j]] > dep[w]) top = fa[top][j]; } sz[w] -= size[top]; if (blg[w] == blg[to[i]]) { vout[vis[blg[w]]] += size[top] - size[to[i]] + 1; } else { cur = to[i]; for (int j=17;~j;j--) { if (dis(fa[cur][j],blg[w]) > dis(blg[to[i]], fa[cur][j])) cur = fa[cur][j]; } vout[vis[blg[to[i]]]] += size[cur] - size[to[i]] + 1; if (dep[fa[cur][0]] > dep[w] && dis(fa[cur][0], blg[w]) == dis(fa[cur][0], blg[to[i]])){ vout[vis[min(blg[w], blg[to[i]])]] += size[fa[cur][0]] - size[cur]; vout[vis[blg[w]]] += size[top] - size[fa[cur][0]]; } else { vout[vis[blg[w]]] += size[top] - size[cur]; } } solve(to[i]); } vout[vis[blg[w]]] += sz[w]; } int main(){ n = read(); for (int i=1;i<n;i++) Add_Edge(read(),read()); DFS(1,1); T = 0; memset(head,0,sizeof(head)); for (int q=read(),lca;q;q--) { m = tot = read(); lca = p[1] = read(); vis[p[1]] = 1; vout[1] = 0; for (int i=2;i<=m;i++) { vis[p[i]=read()] = i; lca = LCA(lca, p[i]); vout[i] = 0; } sort(p+1, p+1+m, CMP); Build(lca); prework_1(lca,-1); prework_2(lca); solve(lca); for (int i=1;i<=m;i++) { printf("%d ",vout[i]); } putchar('\n'); for (int i=1;i<=tot;i++) { vis[p[i]] = head[p[i]] = 0; } T = 0; } return 0; }
Muchos Gracias for your blog article.Really thank you! Awesome.
I value the article post.Much thanks again. Cool.
A round of applause for your article post.Really looking forward to read more. Will read on…
Great blog article.Much thanks again.
I truly appreciate this blog.Much thanks again. Really Great.
Fantastic blog post. Keep writing.
I loved your blog post.Really thank you! Much obliged.
Very neat post.Much thanks again. Fantastic.
I really enjoy the article post.
I really liked your blog post.Really looking forward to read more. Will read on…
I really like and appreciate your article post.Really thank you! Really Great.
I am so grateful for your blog.Thanks Again. Will read on…
Very good article post.Much thanks again. Cool.
I truly appreciate this blog. Want more.
Thanks a lot for the article post.Thanks Again. Much obliged.
Looking forward to reading more. Great article post.Much thanks again. Fantastic.
Major thanks for the blog post.Really thank you! Really Cool.
Thanks-a-mundo for the article post.Really looking forward to read more.
Really enjoyed this blog post.Really thank you! Will read on…
I cannot thank you enough for the blog.Much thanks again. Great.
It is really a great and helpful piece of information. I am
happy that you just shared this useful info with us.
Please stay us informed like this. Thank you for sharing.
Great article post.Really looking forward to read more. Really Cool.
Im grateful for the article.Really thank you! Fantastic.
Thanks so much for the article post.Really looking forward to read more.
Say, you got a nice article.Really looking forward to read more. Cool.
I really enjoy the post.Really looking forward to read more. Awesome.
I’m not that much of a internet reader to be honest but your blogs really nice,
keep it up! I’ll go ahead and bookmark your site to come back later.
Many thanks
Great, thanks for sharing this blog.Really looking forward to read more. Awesome.
Enjoyed every bit of your blog article.Much thanks again. Much obliged.
I cannot thank you enough for the article.Really looking forward to read more. Want more.
My brother suggested I may like this web site. He was totally right.
This put up actually made my day. You can not believe simply how much time I had
spent for this info! Thanks!
Very neat blog. Keep writing.
wow, awesome blog post.Much thanks again.
Very informative post.Much thanks again. Want more.
I cannot thank you enough for the article post.Much thanks again. Will read on…
Very neat blog article.Really thank you! Much obliged.
Thanks again for the post.Thanks Again. Keep writing.
Hey, thanks for the article post.Much thanks again. Want more.
Enjoyed every bit of your article post.Much thanks again. Cool.
I appreciate you sharing this article.Thanks Again.
Hey there, You’ve done a great job. I will definitely digg it and personally suggest to my friends.
I am confident they’ll be benefited from this website.
I really like this website , and hope you will write more ,thanks a lot for your information.
Im thankful for the article post.Thanks Again. Cool.
A big thank you for your blog.Really thank you! Much obliged.
I truly appreciate this article. Great.
Thanks for the article.Really thank you! Really Cool.
Thanks for sharing such a nice idea, post is nice, thats why i have
read it fully
Looking forward to reading more. Great blog article.Thanks Again. Want more.
I appreciate you sharing this post. Keep writing.
I really liked your article.Thanks Again. Much obliged.
Im grateful for the blog post.Really looking forward to read more. Cool.
Muchos Gracias for your blog article. Cool.
I’ve learn several excellent stuff here. Certainly worth bookmarking for
revisiting. I surprise how a lot effort you place to create
this type of fantastic informative web site.
Thank you for your blog article.Much thanks again. Will read on…
Very informative blog article.Thanks Again. Great.
I loved your article post.Thanks Again.
Really enjoyed this post.Really looking forward to read more. Awesome.
Great, thanks for sharing this blog article.Really looking forward to read more. Great.
Wow, this article is nice, my sister is analyzing these things,
so I am going to tell her.
I love what you guys tend to be up too. This kind of clever work and reporting! Keep up the wonderful works guys I’ve added you guys to blogroll.
I appreciate you sharing this article.Really thank you! Really Great.
Say, you got a nice article. Fantastic.
Hey, thanks for the blog post.Much thanks again. Really Cool.
Hi just wanted to give you a quick heads up and let you know a few of the images aren’t loading correctly.
I’m not sure why but I think its a linking
issue. I’ve tried it in two different internet browsers and both show the same results.
Very good blog.Thanks Again. Really Cool.
Hey, thanks for the post.Really thank you! Much obliged.
A round of applause for your blog post.Really thank you! Great.
I really enjoy the post.Thanks Again. Will read on…
Im obliged for the post. Much obliged.
I loved your post.Really looking forward to read more. Really Great.
A round of applause for your article.Thanks Again. Awesome.
Major thanks for the blog post. Cool.
I cannot thank you enough for the blog post.Thanks Again. Want more.
Fantastic article post. Fantastic.
Im grateful for the post.Really looking forward to read more. Awesome.
Very neat blog.Thanks Again. Fantastic.
Wow, great blog. Awesome.
Muchos Gracias for your article.Really looking forward to read more. Really Cool.
Awesome post.Really looking forward to read more. Cool.
Hi! I could have sworn I’ve visited your blog before
but after browsing through some of the articles I realized it’s new
to me. Nonetheless, I’m certainly pleased I discovered it and I’ll be bookmarking it and checking back regularly!
My brother recommended I may like this blog.
He was once entirely right. This submit truly made my day. You can not consider just how much time
I had spent for this info! Thank you!
What a stuff of un-ambiguity and preserveness of precious experience about unpredicted feelings.
Very neat post. Awesome.
Im grateful for the article post.Really looking forward to read more.
Thanks-a-mundo for the blog post.Thanks Again. Fantastic.
Just desire to say your article is as surprising. The
clearness in your post is just nice and i could assume
you are an expert on this subject. Fine with your permission allow me to grab your RSS feed to keep
updated with forthcoming post. Thanks a million and please carry on the rewarding work.
Thank you for your blog article.Really thank you! Want more.
Muchos Gracias for your article.Really looking forward to read more. Fantastic.
Very neat blog article.Much thanks again.
I really like your blog.. very nice colors & theme.
Did you design this website yourself or did you
hire someone to do it for you? Plz respond as I’m looking to
construct my own blog and would like to know where u got this from.
appreciate it
I loved your blog article.Thanks Again. Great.
Thanks for the blog. Really Great.
Looking forward to reading more. Great blog post. Fantastic.
Great, thanks for sharing this blog post.Much thanks again. Will read on…
I really enjoy the blog post.Really looking forward to read more. Awesome.
Awesome blog post.Really thank you! Really Cool.
Very good post. Awesome.
I’m not sure why but this site is loading extremely slow for me.
Is anyone else having this issue or is it a problem on my end?
I’ll check back later and see if the problem still exists.
Thanks-a-mundo for the article.Really looking forward to read more. Cool.
I think this is a real great blog. Great.
Muchos Gracias for your article post.Really looking forward to read more. Cool.
Hey great website! Does running a blog like
this take a large amount of work? I have very little understanding of programming however I was hoping to
start my own blog soon. Anyhow, should you have any recommendations or techniques for new blog owners please
share. I know this is off topic but I simply needed
to ask. Kudos!
Im grateful for the blog. Will read on…
Thanks so much for the article post.Much thanks again. Fantastic.
I loved your article post.Really thank you!
I truly appreciate this article.Really thank you! Cool.
Fantastic article.Really looking forward to read more. Really Cool.
I cannot thank you enough for the blog.Really thank you! Will read on…
I really liked your article post. Really Cool.
This is my first time go to see at here and i am
actually happy to read everthing at single place.
Thanks-a-mundo for the article.Much thanks again. Fantastic.
Thank you for your blog. Awesome.
Im obliged for the article. Really Great.
I value the post.Much thanks again. Want more.
wow, awesome blog article. Will read on…
Thanks for sharing, this is a fantastic post. Really Great.
Really informative blog.Much thanks again. Awesome.
Very good blog post.Really thank you! Really Great.
Hey, thanks for the post.Really thank you! Will read on…
Thanks so much for the blog post. Really Cool.
Hey, thanks for the blog article. Cool.
Awesome blog.Really thank you! Awesome.
I really like and appreciate your article post.Really looking forward to read more. Cool.
I value the blog.Really thank you! Keep writing.
Really informative blog.Really looking forward to read more. Really Cool.
Hey, thanks for the post.Really looking forward to read more. Much obliged.
I value the article post.Really looking forward to read more. Really Great.
I loved your article post.Really looking forward to read more. Keep writing.
Thanks for the article post.Really looking forward to read more. Will read on…
Really appreciate you sharing this blog. Keep writing.
Im grateful for the blog post.Much thanks again.
Very informative blog post.Really thank you! Will read on…
Thanks-a-mundo for the article. Awesome.
I really like and appreciate your post.Much thanks again. Keep writing.
Very informative post.Thanks Again. Great.
Im grateful for the blog article.Really thank you! Cool.
Thanks a lot for the article post.Really looking forward to read more. Cool.
Really appreciate you sharing this blog article.Really looking forward to read more. Really Great.
Thanks a lot for the article. Really Cool.
Very informative blog. Much obliged.
A round of applause for your article post.Really thank you! Want more.
I cannot thank you enough for the article post.Really looking forward to read more. Great.
Really enjoyed this article post.Thanks Again. Cool.
wow, awesome blog post.Really looking forward to read more. Really Great.
I value the blog article.Really thank you! Really Great.
A big thank you for your blog article.Thanks Again. Want more.
Major thankies for the blog article.Thanks Again. Really Cool.
Awesome post.Thanks Again. Much obliged.
Great blog.Really looking forward to read more. Cool.
Hey, thanks for the post.Really looking forward to read more. Fantastic.
Awesome post.Really thank you! Want more.
Undeniably imagine that that you said. Your favourite reason seemed to be on the
net the easiest factor to keep in mind of. I say to you, I
definitely get annoyed while people consider concerns that they just don’t know
about. You managed to hit the nail upon the highest and defined out the whole thing with
no need side-effects , other people could take a signal.
Will likely be again to get more. Thank you
hey there and thank you for your info – I have definitely picked up something new from proper here. I did alternatively expertise several technical points using this site, since I skilled to reload the web site many times previous to I may just get it to load properly. I have been thinking about in case your web host is OK? Not that I’m complaining, however sluggish loading instances instances will sometimes impact your placement in google and could injury your high-quality score if advertising and ***********|advertising|advertising|advertising and *********** with Adwords. Anyway I’m including this RSS to my e-mail and could look out for a lot more of your respective intriguing content. Make sure you update this again soon..
I really like and appreciate your post.Really thank you! Really Cool.
I am so grateful for your blog.Much thanks again.
Thanks for sharing, this is a fantastic blog article.Really thank you! Will read on…
I truly appreciate this blog post.Thanks Again. Keep writing.
wow, awesome article post.Really thank you! Want more.
Enjoyed every bit of your blog post.Thanks Again. Keep writing.
I appreciate you sharing this blog.Much thanks again.
I really liked your post.Much thanks again. Much obliged.
Very good blog post.Really thank you! Much obliged.
A big thank you for your blog.Really thank you! Want more.
Very neat article post.Much thanks again. Keep writing.
Wow, great blog post.Really looking forward to read more. Really Cool.
Thanks so much for the article post.Really looking forward to read more. Will read on…
I really enjoy the blog post.Thanks Again. Awesome.
Thanks for sharing, this is a fantastic blog.Thanks Again. Keep writing.
Appreciate you sharing, great blog post.Really looking forward to read more. Really Cool.
Thanks a lot for the post.Much thanks again. Keep writing.
Thanks-a-mundo for the article.Really looking forward to read more. Really Cool.
I truly appreciate this blog.Much thanks again. Great.
Very good article.Really looking forward to read more. Awesome.
Great, thanks for sharing this blog.Thanks Again. Great.
I value the blog post. Really Cool.
Great article.Really thank you! Will read on…
A big thank you for your blog.Really looking forward to read more. Want more.
Im grateful for the article post.Thanks Again. Fantastic.
Thanks again for the post.Really looking forward to read more. Want more.
A big thank you for your blog post.Really thank you! Cool.
I truly appreciate this blog post.Really thank you! Want more.
Very informative article post.Really looking forward to read more. Keep writing.
Im grateful for the blog post.Really thank you! Great.
Great post.Really thank you!
I am so grateful for your article post.Thanks Again. Want more.
A big thank you for your post.Much thanks again. Great.
Appreciate you sharing, great article.Much thanks again. Cool.
Thanks so much for the blog. Keep writing.
Enjoyed every bit of your blog post.Much thanks again. Awesome.
Very good article.Really looking forward to read more. Really Cool.
Thanks for sharing, this is a fantastic article.Really looking forward to read more. Much obliged.
Thanks for the blog post.Thanks Again. Really Cool.
wow, awesome article post.Really thank you! Really Cool.
Awesome blog article.Really looking forward to read more. Will read on…