相关链接
题目传送门:http://codeforces.com/problemset/gymProblem/100633/D
中文题面:http://paste.ubuntu.com/23661606/
解题报告
直接考虑将其用点分树搞
对于每一个合法的染色,我们尝试在第一个将染色点a
和被染色点b
分开的分治点c
处进行更新
因为是第一个分开的分治点,所以a、b一定在c的不同子树中
不妨设a的染色范围为d,那么对于任意点b来讲,距离c的距离 <= d-dis(a,c)就好
于是修改操作就暴力爬树高,维护一个单调栈
查询操作也是暴力爬树高,在每一个单调栈那里二分出最后生效的染色点即可
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100000+9; const int M = N << 1; const int L = 20; const int INF = 1e9; int head[N],to[M],nxt[M],cost[M],dis[N],dep[N]; int n,m,fa[N][L]; inline int read() { char c=getchar(); int f=1,ret=0; 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, int w) { static int T = 0; to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w; to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w; } 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) { dis[to[i]] = dis[w] + cost[i]; DFS(to[i], w); } } } inline int DIS(int x, int y) { int ret = dis[x] + dis[y]; if (dep[x] < dep[y]) swap(x, y); for (int i=L-1;~i;i--) if (dep[fa[x][i]] >= dep[y]) x = fa[x][i]; if (x == y) return ret - dis[x] * 2; for (int i=L-1;~i;i--) { if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return ret - dis[fa[x][0]] * 2; } class Node_Based_Divide_and_Conquer{ int cur_ans,root,area_size,rod[N][L]; int sum[N],vis[N],anc[N][L],len[N]; struct Data{ int x,y,z; inline bool operator < (const Data &B) const {return x < B.x;} inline bool operator <= (const Data &B) const {return x <= B.x;} }tmp; vector<Data> stk[N]; vector<Data>::reverse_iterator itr; public: inline void init() { area_size = n; cur_ans = INF; Get_Root(1, 1); len[root] = 1; Build(root, n); } inline void modify(int w, int d, int c, int id) { tmp.y = c; tmp.z = id; for (int i=0,p;i<len[w];i++) { p = anc[w][i]; tmp.x = d - rod[w][i]; if (tmp.x >= 0) { while (!stk[p].empty() && stk[p].back() <= tmp) stk[p].pop_back(); stk[p].push_back(tmp); } } } inline int query(int w) { Data ret={0,0,0}; for (int i=0,p;i<len[w];i++) { p = anc[w][i]; tmp.x = rod[w][i]; itr = lower_bound(stk[p].rbegin(), stk[p].rend(), tmp); if (itr != stk[p].rend() && ret.z < itr->z) ret = *itr; } return ret.y; } private: void Get_Root(int w, int f) { int mx = 0; sum[w] = 1; for (int i=head[w];i;i=nxt[i]) { if (!vis[to[i]] && to[i] != f) { Get_Root(to[i], w); sum[w] += sum[to[i]]; mx = max(mx, sum[to[i]]); } } mx = max(mx, area_size - sum[w]); if (mx < cur_ans) { cur_ans = mx; root = w; } } void Build(int w, int sz) { vis[w] = 1; anc[w][0] = w; for (int i=head[w];i;i=nxt[i]) { if (!vis[to[i]]) { area_size = sum[to[i]] < sum[w]? sum[to[i]]: sz - sum[w]; cur_ans = INF; Get_Root(to[i], w); len[root] = len[w] + 1; memcpy(anc[root]+1, anc[w], sizeof(anc[w])-4); Build(root, area_size); } } for (int i=1;i<len[w];i++) rod[w][i] = DIS(w, anc[w][i]); } }NDC; int main() { n = read(); for (int i=1,u,v;i<n;i++) { u = read(); v = read(); Add_Edge(u, v, read()); } DFS(1, 1); for (int j=1;j<L;j++) for (int i=1;i<=n;i++) fa[i][j] = fa[fa[i][j-1]][j-1]; NDC.init(); m = read(); for (int i=1,v,d,c;i<=m;i++) { if (read() == 1) { v = read(); d = read(); NDC.modify(v, d, read(), i); } else printf("%d\n",NDC.query(read())); } return 0; }
Muchos Gracias for your article. Great.
Everything is very open with a very clear explanation of the issues. It was definitely informative.
I really enjoy the blog.Really thank you! Awesome.
I loved your blog.Really looking forward to read more. Keep writing.
Im obliged for the post.Really thank you! Will read on…
Very good blog.Really looking forward to read more. Will read on…
Appreciate you sharing, great article.Much thanks again. Great.
Major thanks for the article post.Really looking forward to read more. Much obliged.
Hey, thanks for the blog post.Really looking forward to read more. Keep writing.
Say, you got a nice blog article.Really thank you! Awesome.
Thanks-a-mundo for the article post.Really thank you! Want more.
Im thankful for the blog article.Much thanks again. Awesome.
Awesome blog post.Much thanks again. Really Great.
Awesome blog article.Really looking forward to read more. Cool.
Thanks a lot for the blog post.Much thanks again. Great.
Im obliged for the article.Really thank you! Really Great.
This is one awesome blog.Much thanks again. Fantastic.
Wow, great article.Much thanks again. Fantastic.
I value the article.Much thanks again. Really Cool.
Great post.Really looking forward to read more. Want more.
I truly appreciate this post. Really Great.
A round of applause for your blog.Much thanks again. Really Cool.
Very good post.Really thank you! Much obliged.
A big thank you for your article. Cool.
Enjoyed every bit of your blog post.Thanks Again. Awesome.
This is one awesome blog post.Really looking forward to read more. Really Cool.
Thanks a lot for the blog post.Thanks Again. Really Cool.
I think this is a real great article post.Really thank you! Great.
Major thanks for the post.Much thanks again. Fantastic.
A big thank you for your post.Really looking forward to read more. Keep writing.
I really enjoy the blog.Much thanks again. Cool.
wow, awesome article. Great.
Im grateful for the article. Cool.
Hello there, I found your web site by means
of Google whilst searching for a comparable matter, your site got here up, it seems
good. I have bookmarked it in my google bookmarks.
Hi there, simply was alert to your weblog via Google, and located that it’s truly informative.
I am gonna watch out for brussels. I will be grateful
if you proceed this in future. Numerous folks will probably be benefited from your writing.
Cheers!
It is perfect time to make some plans for the future and it is time
to be happy. I have read this post and if I could I wish to suggest you few interesting things or
suggestions. Maybe you can write next articles referring to this article.
I wish to read even more things about it!
I think this is a real great blog.Really thank you! Cool.
Wow, great post.Really thank you! Awesome.
I read this post completely regarding the comparison of most recent and earlier technologies, it’s amazing article.
Really informative blog post. Cool.
Very informative blog article.Much thanks again. Much obliged.
I really enjoy the blog post.Much thanks again. Really Cool.
Very good blog. Want more.
I really like and appreciate your blog article. Much obliged.
Thanks-a-mundo for the blog post.Thanks Again. Want more.
A round of applause for your blog.Really thank you! Awesome.
I pay a visit every day some sites and websites to read articles, but this blog offers quality based content.
Very informative article post.Thanks Again. Fantastic.
Thanks a lot for the blog post.Really looking forward to read more. Keep writing.
I really like it when people come together and share views.
Great blog, stick with it!
Thanks again for the post. Great.
This is a topic that is near to my heart… Cheers!
Where are your contact details though?
Great article.Much thanks again. Cool.
Appreciate you sharing, great blog post. Want more.
Great post.Thanks Again. Fantastic.
Fastidious replies in return of this issue with solid arguments and describing all concerning that.
Very good post.Really looking forward to read more.
Say, you got a nice post.Thanks Again. Really Great.
Very good blog.Really thank you!
Very neat blog.Really thank you! Great.
Awesome blog article. Keep writing.
Thanks again for the post.Really looking forward to read more. Awesome.
Hello are using WordPress for your site platform?
I’m new to the blog world but I’m trying to get started and create my own. Do you
need any coding knowledge to make your own blog?
Any help would be greatly appreciated!
wow, awesome blog article.Thanks Again. Keep writing.
I really like and appreciate your article post.Much thanks again. Really Cool.
Say, you got a nice post.Thanks Again. Really Great.
A big thank you for your blog article. Really Great.
wow, awesome blog post.Really thank you! Cool.
I loved your article.Really looking forward to read more.
It’s an amazing paragraph designed for all the online
people; they will obtain advantage from it I am sure.
Thanks so much for the post.Much thanks again. Fantastic.
Major thankies for the blog.Thanks Again. Fantastic.
I value the article post.Really thank you! Great.
Im thankful for the blog.Thanks Again. Keep writing.
Awesome article.Really thank you! Awesome.
Thanks so much for the blog.Much thanks again. Much obliged.
Does your site have a contact page? I’m having trouble locating it but, I’d like to shoot you an email.
I’ve got some ideas for your blog you might be interested
in hearing. Either way, great site and I look forward to seeing it develop over
time.
Thanks so much for the article post.Thanks Again.
I really enjoy the blog post.Thanks Again. Will read on…
I am no longer certain where you are getting your information, however great topic.
I must spend a while studying much more or figuring out more.
Thanks for great info I was in search of this info for my mission.
Thanks for the blog post.Thanks Again. Cool.
Major thanks for the post.Thanks Again.
I think that is among the most vital info for me. And i am satisfied reading your article.
However wanna observation on few general things,
The web site taste is wonderful, the articles is in point of fact
excellent : D. Just right activity, cheers
I value the blog article.Thanks Again. Really Great.
Thanks a lot for the post.Much thanks again. Keep writing.
Hi there! I know this is kinda off topic but I was wondering which blog platform
are you using for this website? I’m getting fed up of WordPress because I’ve had problems with hackers and I’m looking at alternatives
for another platform. I would be great if you could point me in the direction of a good platform.
I really like and appreciate your blog article.Thanks Again. Want more.
Thanks again for the post.Thanks Again. Really Cool.
This is one awesome blog post.Really thank you! Really Cool.
Im obliged for the blog article.Really thank you! Really Cool.
Thanks for sharing, this is a fantastic article.Much thanks again. Really Great.
Really enjoyed this article post. Will read on…
Really enjoyed this post.Really thank you! Want more.
Awesome blog.Really thank you! Really Cool.
Fantastic blog article.Much thanks again. Cool.
Major thanks for the article.Really looking forward to read more. Want more.
Thanks so much for the blog article.Thanks Again. Awesome.
Hey there! I know this is kind of off topic but I was wondering which blog platform are you using for this website?
I’m getting fed up of WordPress because I’ve had issues with hackers and
I’m looking at alternatives for another platform.
I would be great if you could point me in the direction of a
good platform.
Enjoyed every bit of your blog.Thanks Again. Really Great.
Say, you got a nice article.Really thank you! Awesome.
I think this is a real great post.Much thanks again. Really Great.
I loved your blog.Thanks Again. Will read on…
wow, awesome article post.Much thanks again. Keep writing.
Enjoyed every bit of your article post.Thanks Again. Want more.
I really like and appreciate your article.Really thank you! Great.
I loved your blog post.Really thank you! Really Great.
I truly appreciate this article.Thanks Again. Great.
Very good post. Fantastic.
Great blog.Thanks Again. Great.
This is one awesome article.Much thanks again. Cool.
Im thankful for the article post.Thanks Again. Cool.
Im obliged for the post.Much thanks again. Will read on…
Thanks for the article post. Awesome.
Fantastic post.Thanks Again. Great.
Thanks for the blog post.Much thanks again. Want more.
I think this is a real great blog article.Really looking forward to read more. Much obliged.
Enjoyed every bit of your blog article.Really thank you! Awesome.
I cannot thank you enough for the article. Much obliged.
I think this is a real great article post.Really thank you! Much obliged.
Im grateful for the blog.Much thanks again. Really Cool.
Im obliged for the article post.Much thanks again. Want more.
I cannot thank you enough for the blog.Much thanks again. Much obliged.
Thanks so much for the post.Much thanks again. Want more.
Fantastic blog article. Awesome.
Write more, thats all I have to say. Literally, it seems as though you relied on the video
to make your point. You obviously know what youre talking about, why throw away your intelligence on just
posting videos to your weblog when you could be giving us
something informative to read?
Very neat blog article.Thanks Again. Really Cool.
I do trust all of the concepts you have presented on your post.
They are very convincing and can definitely work. Nonetheless,
the posts are very quick for newbies. May you please extend them a bit from subsequent time?
Thanks for the post.
Hi i am kavin, its my first time to commenting anywhere, when i read this piece of writing i thought i could also make comment due to this sensible post.
Very neat blog article.Really looking forward to read more.
I think this is a real great article post. Really Great.
Looking forward to reading more. Great blog post.Really thank you! Cool.
Thanks again for the blog.Really looking forward to read more. Fantastic.
Having read this I believed it was extremely informative.
I appreciate you spending some time and effort to put this informative article
together. I once again find myself spending way too much time both
reading and posting comments. But so what, it was still worthwhile!
Awesome blog.Much thanks again. Really Cool.
Muchos Gracias for your article post.Thanks Again. Cool.
I loved your blog article.Thanks Again. Keep writing.
Very good post.Really looking forward to read more. Great.
I cannot thank you enough for the post. Really Cool.
Thanks-a-mundo for the article.Really looking forward to read more. Fantastic.
I really liked your blog article.Really thank you! Much obliged.
Saved as a favorite, I really like your blog!
Enjoyed every bit of your post.Really thank you! Awesome.
Looking forward to reading more. Great post.Really looking forward to read more. Much obliged.
Im grateful for the article.Much thanks again. Really Great.
Hey, thanks for the article post. Really Great.
Looking forward to reading more. Great post.
Major thankies for the post.Really looking forward to read more. Awesome.
Great blog article.Much thanks again. Really Cool.
What’s Going down i am new to this, I stumbled upon this I’ve found It
positively useful and it has aided me out loads. I hope to give a contribution & assist different users like its helped me.
Great job.
A round of applause for your blog post.Much thanks again. Cool.
This is one awesome blog.Much thanks again. Keep writing.
Hi! Do you know if they make any plugins to help with SEO?
I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good results.
If you know of any please share. Many thanks!
wow, awesome article post.Really thank you! Cool.
Very nice post. I just stumbled upon your weblog and wished to say that I’ve really enjoyded surfing around your blog posts. After all I will be subscribing to your feed and I hope you write again very soon!
A big thank you for your blog.Really thank you! Want more.
I value the article.Thanks Again. Cool.
Great artical, had no problems printing this page either.
I really liked your blog. Cool.
I truly appreciate this article post.Much thanks again. Much obliged.
Thanks for the article.Thanks Again. Awesome.
Muchos Gracias for your article post.Really looking forward to read more. Keep writing.
Really informative blog.Really looking forward to read more. Cool.
Major thanks for the post.Thanks Again. Will read on…
I appreciate you sharing this blog article.Much thanks again. Great.
Very neat blog.Really thank you! Cool.
Appreciate you sharing, great blog.Really looking forward to read more. Really Cool.
wow, awesome article.Really looking forward to read more. Awesome.
Great, thanks for sharing this article.Really looking forward to read more. Keep writing.
Awesome blog post.Thanks Again. Really Great.
I really enjoy the post.Much thanks again. Keep writing.
I truly appreciate this post.Thanks Again. Much obliged.
Thanks-a-mundo for the blog article. Really Cool.
Im obliged for the blog post.Much thanks again. Cool.
Great blog post.Much thanks again. Awesome.
You can definitely see your enthusiasm in the article you write.
The arena hopes for more passionate writers such as you who are not
afraid to say how they believe. At all times go after your heart.
Very good blog post.
Thank you ever so for you post.Thanks Again. Keep writing.
Hey, thanks for the blog article.Really thank you! Keep writing.
Thanks a lot for the post.Much thanks again. Will read on…
It’s truly a great and useful piece of info. I’m happy that you just shared this
helpful information with us. Please stay us up
to date like this. Thank you for sharing.
I value the post.Really thank you! Will read on…
Great blog here! Also your web site loads up very fast!
What host are you using? Can I get your affiliate link to your host?
I wish my web site loaded up as quickly as yours lol
Great blog post.Thanks Again. Cool.
Awesome blog.Really looking forward to read more. Cool.
Really appreciate you sharing this article post.Thanks Again. Really Cool.
Appreciate you sharing, great blog post.Much thanks again. Great.
I appreciate you sharing this post.Thanks Again. Awesome.
Thank you ever so for you blog.Really looking forward to read more.
Thanks a lot for the post.Much thanks again. Will read on…
Really appreciate you sharing this blog post.Really thank you! Keep writing.
Really informative article post.Much thanks again. Great.
I think this is a real great blog article.Thanks Again. Awesome.
Im obliged for the article. Really Cool.
Muchos Gracias for your article post.Thanks Again. Great.
Major thanks for the post.Much thanks again. Will read on…
Very informative article post.Thanks Again. Keep writing.
Very good post.Thanks Again. Really Great.
Muchos Gracias for your post. Much obliged.
Very good blog article. Cool.
Thank you ever so for you blog.Thanks Again. Will read on…
Fantastic article.Really thank you! Much obliged.
Im grateful for the post.Really looking forward to read more. Much obliged.
Looking forward to reading more. Great blog article.Really thank you! Really Great.
Major thankies for the blog.Thanks Again. Keep writing.
Thanks-a-mundo for the blog article.Really thank you! Cool.
Im thankful for the blog article.Thanks Again. Awesome.
Good day! I could have sworn I’ve been to this website before but after looking at some of the articles
I realized it’s new to me. Anyways, I’m certainly pleased I discovered it and I’ll
be book-marking it and checking back often!
I am writing to let you know of the perfect experience my cousin’s child developed browsing your site. She came to understand so many issues, which included what it’s like to have a wonderful giving character to make many others clearly master specific grueling subject matter. You truly exceeded readers’ expected results. Thanks for distributing those essential, safe, explanatory and in addition fun tips on your topic to Emily.
Thanks for the blog.Much thanks again. Want more.
How long does a copyright last on newspaper articles?. . If a service copies newspapers articles and then posts it in a database on the Internet, is there also a copyright on the Internet content?.
Looking forward to reading more. Great article.Much thanks again. Much obliged.
Enjoyed every bit of your article post. Cool.
Very good blog.Really looking forward to read more. Awesome.
Really enjoyed this blog article.Really thank you! Want more.
Really enjoyed this article post.Thanks Again. Awesome.
Thank you ever so for you article. Much obliged.
I really liked your article.Really looking forward to read more. Really Cool.
A big thank you for your post.Really thank you! Great.
Thank you ever so for you article.
Great, thanks for sharing this blog article.Really thank you! Much obliged.
Thank you for your article post.Thanks Again. Awesome.
I really liked your blog.Thanks Again. Great.
Very informative blog article.Really thank you! Keep writing.
I appreciate you sharing this blog article.
Thanks again for the post.Really looking forward to read more. Cool.
I really enjoy the blog.Really looking forward to read more. Great.
Hey, thanks for the article.Much thanks again.
Looking forward to reading more. Great blog.Thanks Again. Great.
What’s up to every body, it’s my first pay a quick visit of this webpage; this website consists of amazing and actually fine information designed for readers.|
Say, you got a nice article post.
Muchos Gracias for your blog.Really thank you! Will read on…
This paragraph presents clear idea in favor of the new viewers of blogging, that truly how to do blogging.|
Definitely believe that which you said. Your favorite justification seemed to be on the internet the easiest thing to be aware of. I say to you, I certainly get annoyed while people think about worries that they plainly don’t know about. You managed to hit the nail upon the top and also defined out the whole thing without having side-effects , people can take a signal. Will probably be back to get more. Thanks|
Very informative blog article. Fantastic.
Awesome article post.
Thanks-a-mundo for the blog.Much thanks again. Great.
Greetings from Carolina! I’m bored to tears at work so I decided to browse your website on my iphone during lunch break. I really like the information you provide here and can’t wait to take a look when I get home. I’m shocked at how quick your blog loaded on my cell phone .. I’m not even using WIFI, just 3G .. Anyways, very good site!|
Thank you for your article.Really looking forward to read more. Fantastic.
Thank you for your blog post.Much thanks again. Will read on…
Enjoyed every bit of your post.Really looking forward to read more.
Appreciate you sharing, great blog.
wow, awesome post.Much thanks again. Fantastic.
Looking forward to reading more. Great article.Thanks Again. Really Cool.
Muchos Gracias for your article post.Really thank you! Will read on…
This paragraph is genuinely a fastidious one it assists new web users, who are wishing in favor of blogging.|
Hey There. I found your blog the usage of msn. That is a very well written article. I’ll be sure to bookmark it and return to read more of your useful info. Thank you for the post. I’ll definitely return.|
wow, awesome article.Thanks Again. Awesome.
Thanks for sharing, this is a fantastic blog.Really thank you! Really Great.
This is one awesome blog article.Much thanks again. Really Great.
Hey exceptional website! Does running a blog similar to this take a large amount of work? I have virtually no expertise in programming however I had been hoping to start my own blog soon. Anyway, should you have any recommendations or techniques for new blog owners please share. I know this is off subject but I simply needed to ask. Thank you!|
A round of applause for your article.Much thanks again. Really Cool.
I have read so many content concerning the blogger lovers but this article is really a pleasant article, keep it up.|
This is really interesting, You are a very skilled blogger. I’ve joined your feed and look forward to seeking more of your fantastic post. Also, I’ve shared your web site in my social networks!|
Very informative blog article.Really looking forward to read more. Much obliged.
Very neat blog article.Much thanks again. Great.
I think what you said made a lot of sense. However, what about this? suppose you wrote a catchier title? I ain’t saying your content isn’t solid, however suppose you added a headline that grabbed a person’s attention? I mean BLOG_TITLE is a little plain. You could peek at Yahoo’s home page and see how they create post titles to grab viewers to click. You might try adding a video or a related pic or two to grab readers interested about everything’ve written. Just my opinion, it might make your posts a little bit more interesting.|
Very good post.Much thanks again. Cool.
Really informative blog.Really thank you! Really Cool.
I really liked your blog article.Really thank you! Much obliged.
Really enjoyed this article post.Thanks Again. Fantastic.
Enjoyed every bit of your article.Really thank you!
Wonderful site. Plenty of helpful info here. I’m sending it to some buddies ans also sharing in delicious. And of course, thank you in your sweat!|
Right here is the perfect site for anyone who wants to find out about this topic. You know a whole lot its almost tough to argue with you (not that I personally will need to…HaHa). You certainly put a fresh spin on a topic that has been written about for decades. Excellent stuff, just wonderful!|
I really enjoy the blog post.Really thank you! Keep writing.
Great article. Will read on…
Say, you got a nice article.Much thanks again. Much obliged.
Thank you ever so for you article.Really looking forward to read more. Really Cool.
Sweet blog! I found it while surfing around on Yahoo News. Do you have any tips on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Thanks|
{