相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3307
神犇题解:http://blog.csdn.net/ww140142/article/details/48660513
解题报告
这题,搬到序列上大家都会啊
就是先把操作打成tag,扔到序列上
然后用线段树扫一遍,统计答案即可
当然线段树合并也很好写啊
也是先搞成tag,然后合并上去,顺便记录一下答案
时间复杂度:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = N << 1; const int G = 7000000; const int INF = 1e9; int n,m,dep[N],ans[N],fa[N][20]; int head[N],to[M],nxt[M]; 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) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } void DFS(int w, int f) { fa[w][0] = f; dep[w] = dep[f] + 1; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { DFS(to[i], w); } } } inline int LCA(int u, int v) { if (dep[u]<dep[v]) swap(u, v); for (int j=19;~j;j--) if (dep[fa[u][j]]>=dep[v]) u = fa[u][j]; if (u == v) return u; for (int j=19;~j;j--) if (fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j]; return fa[u][0]; } class Segment_Tree{ int cnt,ch[G][2],mx[G],id[G],root[N]; public: inline void merge(int x, int y) { root[x] = Merge(root[x], root[y]); } inline void insert(int w, int p, int t) { insert(root[w], 1, INF, p, t); } inline int query(int w) { return mx[root[w]]? id[root[w]]: 0; } private: int Merge(int x, int y) { if (!x || !y) return x + y; if (!ch[x][0] && !ch[x][1]) { mx[x] += mx[y]; return x; } else { ch[x][0] = Merge(ch[x][0], ch[y][0]); ch[x][1] = Merge(ch[x][1], ch[y][1]); if (mx[ch[x][0]] >= mx[ch[x][1]]) id[x] = id[ch[x][0]], mx[x] = mx[ch[x][0]]; else id[x] = id[ch[x][1]], mx[x] = mx[ch[x][1]]; return x; } } void insert(int &w, int l, int r, int p, int delta) { if (!w) w = ++cnt; if (l == r) { mx[w] += delta; id[w] = l; } else { int mid = l + r + 1 >> 1; if (p < mid) insert(ch[w][0], l, mid-1, p, delta); else insert(ch[w][1], mid, r, p, delta); if (mx[ch[w][0]] >= mx[ch[w][1]]) id[w] = id[ch[w][0]], mx[w] = mx[ch[w][0]]; else id[w] = id[ch[w][1]], mx[w] = mx[ch[w][1]]; } } }ST; void solve(int w, int f) { for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { solve(to[i], w); ST.merge(w, to[i]); } } ans[w] = ST.query(w); } int main() { n = read(); m = read(); for (int i=1;i<n;i++) AddEdge(read(), read()); DFS(1, 1); for (int j=1;j<20;j++) { for (int i=1;i<=n;i++) { fa[i][j] = fa[fa[i][j-1]][j-1]; } } for (int i=1,u,v,lca,c;i<=m;i++) { u = read(); v = read(); c = read(); lca = LCA(u, v); ST.insert(u, c, 1); ST.insert(v, c, 1); ST.insert(lca, c, -1); if (lca-1) ST.insert(fa[lca][0], c, -1); } solve(1, 1); for (int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }
Very informative article. Fantastic.
Major thankies for the post.Really looking forward to read more. Really Cool.
Im thankful for the post.Really looking forward to read more. Really Cool.
Very informative blog post.Really thank you!
Very informative article. Great.
Very good article.Really thank you!
Im grateful for the post.Really looking forward to read more. Cool.
A big thank you for your blog post.Really thank you! Awesome.
Great, thanks for sharing this blog article.Really thank you! Really Cool.
Wow, great article post.Really thank you! Awesome.
Muchos Gracias for your blog.Really looking forward to read more. Awesome.
A round of applause for your article.Thanks Again. Will read on…
704958 589248These kinds of Search marketing boxes normally realistic, healthy and balanced as a result receive just about every customer service necessary for some product. Link Building Services 418921
Thanks a lot for the post.Really thank you! Will read on…
I really like and appreciate your blog. Cool.
Major thankies for the article post.Really looking forward to read more. Much obliged.
Say, you got a nice article.Thanks Again. Want more.
Great blog post.Thanks Again. Will read on…
Appreciate you sharing, great article.Much thanks again. Really Cool.
Hey, thanks for the blog article.Much thanks again. Really Cool.
Hey, thanks for the post.Really looking forward to read more.
Hey, thanks for the post.Really looking forward to read more. Will read on…
Thank you for your article.Really looking forward to read more. Fantastic.
Major thanks for the blog. Much obliged.
Thanks for sharing, this is a fantastic article. Fantastic.
Appreciate you sharing, great post. Fantastic.
A big thank you for your post.Much thanks again. Awesome.
Enjoyed every bit of your article.Much thanks again. Really Great.
I cannot thank you enough for the article post.Thanks Again. Awesome.
Fantastic blog article.Much thanks again.
I value the blog post.Much thanks again. Keep writing.
I value the blog post.Really thank you! Will read on…
A big thank you for your blog article.Really thank you!
Awesome blog.Really looking forward to read more. Want more.
Very informative article post.Thanks Again. Really Cool.
Really appreciate you sharing this article post.Really looking forward to read more. Really Great.
I think this is a real great article post.Thanks Again. Really Cool.
Great, thanks for sharing this blog.Thanks Again. Keep writing.
Wow, great blog post. Really Cool.
Thanks-a-mundo for the blog post.Much thanks again. Great.
I loved your blog post.Really looking forward to read more. Awesome.
I truly appreciate this post.Much thanks again.
I loved your blog. Really Cool.
Im thankful for the blog post.Really looking forward to read more. Really Cool.
I really enjoy the article post.Really thank you! Will read on…
Really informative article.Really looking forward to read more. Awesome.
Really enjoyed this blog.Much thanks again. Great.
This is one awesome article post.Thanks Again.
Thank you for your blog.Really thank you! Cool.
This is one awesome blog post.Really thank you! Want more.
Thanks a lot for the blog article. Want more.
I really like and appreciate your blog article.Thanks Again.
Wow, great blog.Really looking forward to read more. Want more.
Hey, thanks for the blog article.Really looking forward to read more. Will read on…
Im thankful for the blog article.Really thank you! Great.
I loved your blog.Much thanks again. Fantastic.
Enjoyed every bit of your article post.Much thanks again. Fantastic.
Very informative article post.Much thanks again. Great.
I was looking at some of your content on this site and I conceive this internet site is very instructive! Retain posting.
I think this is a real great post.Much thanks again. Will read on…
Great blog.Really thank you! Much obliged.
Enjoyed every bit of your article.Thanks Again. Really Cool.
Muchos Gracias for your blog post.Much thanks again. Will read on…
Thanks for sharing, this is a fantastic post.Much thanks again. Want more.
A round of applause for your blog.Really looking forward to read more. Want more.
Appreciate you sharing, great article. Keep writing.
Thanks a lot for the article post.
Enjoyed every bit of your post.Much thanks again. Awesome.
I truly appreciate this post.Really looking forward to read more. Really Cool.
Thanks a lot for the blog post.Much thanks again. Really Great.
Thanks for the article.Really looking forward to read more. Want more.
Thanks for the article. Really Cool.
wow, awesome article. Keep writing.
Wow, great article.Much thanks again. Fantastic.
Really enjoyed this blog post.Thanks Again. Will read on…
Im thankful for the article post.Really thank you! Awesome.
Very informative post.Thanks Again. Great.
Very neat article.Thanks Again. Fantastic.
I really like and appreciate your blog.Thanks Again. Want more.
Very good blog.Really looking forward to read more. Really Great.
Really appreciate you sharing this blog.Thanks Again. Keep writing.
I really enjoy the article.Really thank you! Really Great.
Hey, thanks for the article post.Really thank you! Great.
Thanks so much for the blog. Much obliged.
Awesome blog. Great.
I value the post.Thanks Again. Really Great.
Thanks a lot for the blog article.Thanks Again. Really Great.
It is actually a great and helpful piece of information. I?¦m glad that you just shared this useful info with us. Please stay us up to date like this. Thank you for sharing.
Major thankies for the article. Keep writing.
Thanks a lot for the post.Really thank you!
Thanks for the blog post.Really looking forward to read more. Awesome.
Im thankful for the blog post.Much thanks again. Will read on…
Appreciate you sharing, great article post.Really looking forward to read more. Really Great.
Major thankies for the blog post.Much thanks again. Cool.
Great, thanks for sharing this article post.Much thanks again. Great.
Im thankful for the blog article.Thanks Again. Keep writing.
Muchos Gracias for your blog.Really looking forward to read more. Keep writing.
I really liked your article post.Really looking forward to read more.
I really liked your article post.Much thanks again. Want more.
Really appreciate you sharing this blog post.Really looking forward to read more. Really Cool.
Enjoyed every bit of your post.Thanks Again. Will read on…
Thanks so much for the blog.Much thanks again. Fantastic.
This is one awesome blog article.Really looking forward to read more. Much obliged.
Thanks-a-mundo for the blog post.Much thanks again. Awesome.
Very neat article. Cool.
Very informative blog.Much thanks again. Really Cool.
Great, thanks for sharing this post.Really thank you!
Really enjoyed this post. Fantastic.
Very informative blog post.Really looking forward to read more. Really Cool.
I am so grateful for your blog post.Thanks Again. Awesome.
Thanks a lot for the post. Awesome.
A big thank you for your blog.Much thanks again. Cool.
Major thanks for the blog. Want more.
Thanks-a-mundo for the post.Thanks Again. Keep writing.
Great blog article.Thanks Again. Much obliged.
I loved your article post.Much thanks again. Great.
I am so grateful for your blog.Really looking forward to read more. Awesome.
Thanks so much for the blog post.Really looking forward to read more. Really Cool.
I really enjoy the article. Great.
I really enjoy the blog post.Much thanks again. Keep writing.
I appreciate you sharing this post.Thanks Again. Want more.
I really like and appreciate your blog.Really looking forward to read more. Will read on…
I really like and appreciate your article.Really thank you! Fantastic.
Thanks again for the article. Really Great.
Really enjoyed this article.Thanks Again. Will read on…
Appreciate you sharing, great article post.Much thanks again. Cool.
Thank you ever so for you post.Really looking forward to read more.
Appreciate you sharing, great article.Really thank you! Really Great.
Thanks-a-mundo for the blog post. Really Great.
I really enjoy the article post.Really thank you! Keep writing.
Major thankies for the post.Much thanks again. Awesome.
Thanks for sharing, this is a fantastic article post.Really looking forward to read more. Really Great.
Thank you for your article post.Much thanks again.
I really like and appreciate your post.Really looking forward to read more. Fantastic.
Im obliged for the article.Thanks Again.
I value the article.Much thanks again. Really Great.
Appreciate you sharing, great article.Really thank you! Will read on…
Im obliged for the blog.Much thanks again. Great.
Fantastic blog post.Really thank you! Keep writing.
I really like and appreciate your blog.Really thank you! Fantastic.
Enjoyed every bit of your blog article.Really looking forward to read more. Great.
Im obliged for the article post.Really looking forward to read more.
Wow, great article. Want more.
Say, you got a nice post.Really looking forward to read more. Fantastic.
Thank you for your blog post.Thanks Again. Cool.
Say, you got a nice article post. Want more.
Fantastic blog article.Really thank you! Really Cool.
Really enjoyed this blog article.Really looking forward to read more. Want more.
Thanks for the article.Really looking forward to read more. Really Cool.
Im thankful for the article.Really thank you! Fantastic.
Really appreciate you sharing this post.Thanks Again. Much obliged.
wow, awesome blog post.Really looking forward to read more. Will read on…
I think this is a real great article.Really thank you! Great.
Say, you got a nice post. Want more.
Say, you got a nice article post. Want more.
Awesome blog article.Much thanks again. Really Cool.
Really informative article.Really thank you! Great.
Thanks again for the blog post.Really thank you!
Looking forward to reading more. Great blog. Really Cool.
I really liked your blog.Much thanks again. Fantastic.
I really liked your blog article. Really Cool.
Thanks a lot for the blog article.Really looking forward to read more. Really Great.
Thanks for the blog. Great.
Major thanks for the blog.Really looking forward to read more. Want more.
Say, you got a nice blog post.Really looking forward to read more. Cool.
I am so grateful for your blog article.Much thanks again.
Really enjoyed this blog.Really thank you! Fantastic.
Appreciate you sharing, great blog article. Want more.
Hey, thanks for the blog article.Really thank you!
Thank you for your blog article.Really looking forward to read more. Fantastic.
I appreciate you sharing this blog. Awesome.
Enjoyed every bit of your blog article.Much thanks again.
Major thanks for the blog.Much thanks again. Will read on…
I think this is a real great blog.Much thanks again. Much obliged.
Really enjoyed this blog article.Really looking forward to read more.
Thanks for sharing, this is a fantastic post.Really thank you!
Looking forward to reading more. Great blog.Really thank you! Cool.
Really enjoyed this post.Thanks Again. Really Cool.
I think this is a real great article post.Much thanks again. Much obliged.
Really appreciate you sharing this article post. Will read on…
Great, thanks for sharing this article post.Much thanks again. Awesome.
Very informative article.Really thank you! Want more.
I really like and appreciate your blog post.Much thanks again. Great.
Im grateful for the article.Much thanks again. Want more.
I truly appreciate this blog article. Awesome.
I value the blog article.Thanks Again. Awesome.
Thanks so much for the blog.Much thanks again. Will read on…
Looking forward to reading more. Great post.Thanks Again. Much obliged.
Thanks for sharing, this is a fantastic article.Really looking forward to read more. Great.
Today, I went to the beach with my kids. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is completely off topic but I had to tell someone!
Thanks again for the blog article.Really thank you! Awesome.
Thanks so much for the article post.Really looking forward to read more. Keep writing.
Great post.Really thank you! Cool.
Enjoyed every bit of your blog article.Really looking forward to read more. Really Cool.
Thank you for your post.
I really enjoy the post.Thanks Again. Really Cool.
I really enjoy the post.Much thanks again.
I value the article post.Really looking forward to read more. Will read on…
A round of applause for your blog. Want more.
I really enjoy the blog article. Cool.
Muchos Gracias for your blog article.Much thanks again. Want more.
Looking forward to reading more. Great article post.Really thank you! Will read on…
Im thankful for the blog article. Want more.
Thanks for the blog post.Really looking forward to read more. Fantastic.
Thank you for your post. Really Great.
I really liked your article.Really thank you! Really Cool.
I really liked your blog. Really Cool.
wow, awesome blog.Really thank you! Cool.
I really liked your blog article.Really looking forward to read more. Great.
I enjoy what you guys tend to be up too. This kind of clever work and exposure! Keep up the good works guys I’ve you guys to my personal blogroll.|
Hi, Neat post. There is an issue together with your web site in web explorer, could test this? IE nonetheless is the marketplace chief and a huge component to people will pass over your magnificent writing because of this problem.|
Awesome blog. Great.
Thanks so much for the blog article.Really thank you! Great.
I savor, result in I found exactly what I used to be having a look for. You have ended my four day lengthy hunt! God Bless you man. Have a nice day. Bye|
Hi there would you mind letting me know which web host you’re utilizing? I’ve loaded your blog in 3 completely different internet browsers and I must say this blog loads a lot faster then most. Can you recommend a good web hosting provider at a fair price? Thanks a lot, I appreciate it!|
I really liked your article.Really looking forward to read more. Want more.
Looking forward to reading more. Great post.Much thanks again. Keep writing.
Hello there, just turned into aware of your blog through Google, and located that it’s truly informative. I am gonna be careful for brussels. I will be grateful when you continue this in future. Lots of folks shall be benefited out of your writing. Cheers!|
Great article! This is the type of info that are meant to be shared around the internet. Disgrace on the search engines for now not positioning this submit upper! Come on over and seek advice from my website . Thanks =)|
wow, awesome post.Really looking forward to read more. Great.
Great blog post.Really thank you! Much obliged.
If you would like to improve your know-how simply keep visiting this web page and be updated with the most recent news update posted here.|
Thanks a lot for the article post.Really looking forward to read more. Keep writing.
Really informative blog.Much thanks again. Keep writing.
I cannot thank you enough for the article post.Thanks Again. Really Great.
Thank you ever so for you blog post.Really looking forward to read more. Really Great.
I think the admin of this web page is really working hard in support of his web site, because here every material is quality based material.|
Thank you for your blog article.Really thank you! Much obliged.
I really like and appreciate your article post. Cool.
It’s awesome to go to see this web site and reading the views of all friends about this post, while I am also keen of getting experience.|
Thanks again for the blog post.Much thanks again. Really Great.
A round of applause for your article.Much thanks again. Great.
Thanks a lot for the blog article.Really looking forward to read more. Keep writing.
This is a topic that is close to my heart… Many thanks! Exactly where are your contact details though?|
Howdy 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 browsers and both show the same outcome.|
Good day! Do you know if they make any plugins to assist with SEO? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good success. If you know of any please share. Cheers!|
Really informative article post.Really looking forward to read more. Really Cool.
If you wish for to increase your know-how simply keep visiting this site and be updated with the most up-to-date news posted here.|
I think this is a real great blog post.Really looking forward to read more. Much obliged.
Hi, I do think this is a great web site. I stumbledupon it 😉 I’m going to revisit yet again since I saved as a favorite it. Money and freedom is the greatest way to change, may you be rich and continue to guide others.|
Very neat blog article.
Very neat blog post.Thanks Again. Awesome.
I appreciate you sharing this blog post. Much obliged.
I truly appreciate this blog.Thanks Again. Fantastic.
Hello! I just wanted to ask if you ever have any problems with hackers? My last blog (wordpress) was hacked and I ended up losing many months of hard work due to no backup. Do you have any methods to protect against hackers?|
I have to thank you for the efforts you have put in writing this blog. I’m hoping to check out 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 website now ;)|
Thanks for sharing, this is a fantastic article.Really looking forward to read more.
Major thanks for the post.Much thanks again. Keep writing.
Heya! I realize this is kind of off-topic but I had to ask. Does running a well-established website such as yours require a lot of work? I am completely new to blogging but I do write in my journal on a daily basis. I’d like to start a blog so I will be able to share my personal experience and thoughts online. Please let me know if you have any kind of recommendations or tips for new aspiring bloggers. Appreciate it!|
Thank you for your article post.Really thank you! Want more.
I am so grateful for your blog post.Much thanks again. Want more.
Hi to all, how is the whole thing, I think every one is getting more from this web site, and your views are nice designed for new people.|
Every weekend i used to visit this web page, as i want enjoyment, since this this site conations really pleasant funny stuff too.|
Paragraph writing is also a fun, if you be acquainted with afterward you can write if not it is difficult to write.|
Everything is very open with a really clear explanation of the challenges. It was truly informative. Your website is very useful. Thanks for sharing!|