相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4817
解题报告
我们发现涂色可以看作LCT的access操作
然后权值就是到根的虚边数
于是用LCT来维护颜色
用线段树配合DFS序来支持查询
时间复杂度:$O(n \log^2 n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = N << 1; const int LOG = 20; int n, m, head[N], nxt[M], to[M]; int in[N], ot[N], dep[N], num[N], ff[N][LOG]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; 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; } inline int LCA(int u, int v) { if (dep[u] < dep[v]) { swap(u, v); } for (int j = LOG - 1; ~j; j--) { if (dep[ff[u][j]] >= dep[v]) { u = ff[u][j]; } } if (u == v) { return u; } for (int j = LOG - 1; ~j; j--) { if (ff[u][j] != ff[v][j]) { u = ff[u][j]; v = ff[v][j]; } } return ff[u][0]; } class SegmentTree{ int root, ch[M][2], tag[M], mx[M]; public: inline void init() { build(root, 1, n); } inline void modify(int l, int r, int d) { modify(root, 1, n, l, r, d); } inline int query(int l, int r = -1) { return query(root, 1, n, l, r >= 0? r: l); } private: inline void PushDown(int w) { if (tag[w]) { int ls = ch[w][0], rs = ch[w][1]; mx[ls] += tag[w]; mx[rs] += tag[w]; tag[ls] += tag[w]; tag[rs] += tag[w]; tag[w] = 0; } } inline int query(int w, int l, int r, int L, int R) { if (L <= l && r <= R) { return mx[w]; } else { PushDown(w); int mid = l + r + 1 >> 1, ret = 0; if (L < mid) { ret = max(ret, query(ch[w][0], l, mid - 1, L, R)); } if (mid <= R) { ret = max(ret, query(ch[w][1], mid, r, L, R)); } return ret; } } inline void modify(int w, int l, int r, int L, int R, int d) { if (L <= l && r <= R) { tag[w] += d; mx[w] += d; } else { PushDown(w); int mid = l + r + 1 >> 1; if (L < mid) { modify(ch[w][0], l, mid - 1, L, R, d); } if (mid <= R) { modify(ch[w][1], mid, r, L, R, d); } mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]); } } inline void build(int &w, int l, int r) { static int cnt = 0; w = ++cnt; if (l == r) { mx[w] = dep[num[l]]; } else { int mid = l + r + 1 >> 1; build(ch[w][0], l, mid - 1); build(ch[w][1], mid, r); mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]); } } }SGT; class LinkCutTree{ int ch[N][2], fa[N]; public: inline void SetFather(int w, int f) { fa[w] = f; } inline void access(int x) { for (int last = 0; x; last = x, x = fa[x]) { splay(x); if (fa[x]) { int p = GetMin(x); SGT.modify(in[p], ot[p], -1); } if (ch[x][1]) { int p = GetMin(ch[x][1]); SGT.modify(in[p], ot[p], 1); } ch[x][1] = last; } } private: inline bool IsRoot(int x) { return !fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x); } inline int GetMin(int x) { return ch[x][0]? GetMin(ch[x][0]): x; } inline void splay(int x) { for (int f, ff; !IsRoot(x); ) { f = fa[x], ff = fa[f]; if (IsRoot(f)) { rotate(x); } else { if ((ch[ff][0] == f) ^ (ch[f][0] == x)) { rotate(x); rotate(x); } else { rotate(f); rotate(x); } } } } inline void rotate(int x) { int f = fa[x], t = ch[f][1] == x; fa[x] = fa[f]; if (!IsRoot(f)) { ch[fa[f]][ch[fa[f]][1] == f] = x; } ch[f][t] = ch[x][t ^ 1]; fa[ch[x][t ^ 1]] = f; ch[x][t ^ 1] = f; fa[f] = x; } }LCT; inline void DFS(int w, int f) { static int ID = 0; LCT.SetFather(w, f); ff[w][0] = f; dep[w] = dep[f] + 1; num[in[w] = ++ID] = w; for (int i = head[w]; i; i = nxt[i]) { if (to[i] != f) { DFS(to[i], w); } } ot[w] = ID; } int main() { n = read(); m = read(); for (int i = 1; i < n; i++) { AddEdge(read(), read()); } DFS(1, 0); for (int j = 1; j < LOG; j++) { for (int i = 1; i <= n; i++) { ff[i][j] = ff[ff[i][j - 1]][j - 1]; } } SGT.init(); for (int i = 1; i <= m; i++) { int opt = read(); if (opt == 1) { LCT.access(read()); } else if (opt == 2) { int u = read(), v = read(), lca = LCA(u, v); printf("%d\n", SGT.query(in[u]) + SGT.query(in[v]) - 2 * SGT.query(in[lca]) + 1); } else { int x = read(); printf("%d\n", SGT.query(in[x], ot[x])); } } return 0; }
Hello to every body, it’s my first go to see of this weblog; this blog contains remarkable and actually excellent information designed for visitors.
You really make it seem so easy with your presentation but I find
this matter to be actually something which I think
I would never understand. It seems too complex and extremely broad for me.
I am looking forward for your next post, I’ll try to get the hang of it!
I am not sure where you’re getting your information, but good
topic. I needs to spend some time learning more or understanding more.
Thanks for great info I was looking for this
information for my mission.
Very good post! We are linking to this particularly great content on our
site. Keep up the great writing.
WOW just what I was searching for. Came here by searching for gamefly free trial
First of all I would like to say great blog! I had a quick question that I’d like
to ask if you do not mind. I was interested to find out how you
center yourself and clear your thoughts before writing.
I’ve had a tough time clearing my thoughts in getting my thoughts out.
I do take pleasure in writing however it just seems like the
first 10 to 15 minutes are lost just trying to figure out how to begin. Any ideas or tips?
Thank you!
I know this if off topic but I’m looking into starting my own weblog
and was curious what all is needed to get set up? I’m assuming having a blog like yours would cost a pretty penny?
I’m not very internet savvy so I’m not 100% certain. Any suggestions or advice would be greatly appreciated.
Appreciate it
Outstanding post but I was wondering if you could write
a litte more on this topic? I’d be very thankful if you could elaborate
a little bit more. Bless you!
Pretty! This was a really wonderful post. Many thanks for supplying this information.
Quality content is the crucial to interest the users to go to see the web page, that’s what this
web page is providing.
When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get four emails with the same comment.
Is there any way you can remove me from that service?
Bless you!
Very nice post. I just stumbled upon your blog and wanted to
say that I have really enjoyed surfing around your blog posts.
In any case I’ll be subscribing to your rss feed and I hope you write
again soon!
I think this is one of the most significant info for me. And
i’m glad reading your article. But want to remark on few general things, The web site style is
wonderful, the articles is really excellent :
D. Good job, cheers
Hey There. I found your blog using msn. This is an extremely well written article.
I’ll be sure to bookmark it and come back to read more of your useful
info. Thanks for the post. I’ll certainly return.
Hello There. I found your weblog the usage of msn. That is a really
smartly written article. I’ll make sure to bookmark it
and return to learn extra of your useful information. Thank you for
the post. I will certainly comeback.
Hi to every one, the contents present at this web page
are genuinely amazing for people knowledge, well, keep up the good work fellows.
For most recent information you have to pay a quick visit internet and on the web I found this web site as a best
site for newest updates.
This is a topic that is near to my heart… Cheers! Where are
your contact details though?
It is in reality a great and useful piece of info.
I am satisfied that you simply shared this useful
information with us. Please keep us informed like
this. Thanks for sharing.
I was wondering if you ever thought of changing the page layout of your site?
Its very well written; I love what youve got to say. But maybe you could a little more
in the way of content so people could connect with it
better. Youve got an awful lot of text for only having one or two images.
Maybe you could space it out better?
Hello, awesome work. I really appeaciate the data you are providing through your site, i have alwasy find it helpful. Keep up the nice work.
Your method of describing all in this paragraph is truly pleasant,
all be able to effortlessly be aware of it, Thanks a
lot.
Wow, wonderful blog format! How lengthy have you been running a blog for?
you made running a blog look easy. The overall look of your site is
excellent, as smartly as the content material!
whoah this weblog is great i love studying your posts.
Stay up the good work! You recognize, many people are hunting round for this
info, you can help them greatly.
I want to to thank you for this wonderful read!! I absolutely loved every little bit of
it. I have you bookmarked to look at new stuff you post…
natalielise plenty of fish
I have read so many articles or reviews concerning the blogger lovers but this piece of writing is actually a fastidious paragraph, keep it up.
I am curious to find out what blog system you happen to be working with?
I’m having some minor security issues with my latest blog and I’d like to
find something more secure. Do you have any
suggestions? plenty of fish natalielise
Everyone loves what you guys are up too. This kind of clever
work and exposure! Keep up the terrific works guys I’ve you guys
to blogroll.
I think this is among the most important info for me. And i am glad reading your article.
But should remark on few general things, The website style is
wonderful, the articles is really nice : D. Good job, cheers
Since the admin of this web page is working,
no doubt very soon it will be renowned, due to its feature contents.
plenty of fish natalielise
Paragraph writing is also a excitement, if you be familiar with afterward you
can write if not it is complex to write.
I think this is one of the most important info for me.
And i’m glad reading your article. But want to remark on some general things,
The site style is wonderful, the articles is really excellent :
D. Good job, cheers
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from you! However, how could we communicate?
Thanks very nice blog!
Wonderful beat ! I would like to apprentice while you amend your website, how
can i subscribe for a weblog site? The account helped me
a appropriate deal. I have been tiny bit acquainted of this your broadcast offered bright transparent concept
You’re so cool! I don’t suppose I’ve read through anything like that before.
So wonderful to find someone with genuine thoughts
on this issue. Seriously.. thanks for starting this up.
This website is something that is required on the
internet, someone with some originality!
I simply could not go away your website before suggesting that
I actually enjoyed the standard info an individual supply in your visitors?
Is going to be again continuously in order to check out new
posts
Hi, Neat post. There’s an issue along with your site in internet
explorer, may check this? IE nonetheless is the market chief and a big part of folks
will leave out your great writing due to this problem.
I’m really loving the theme/design of your blog.
Do you ever run into any web browser compatibility issues?
A couple of my blog audience have complained about my blog not working correctly in Explorer but looks great in Safari.
Do you have any ideas to help fix this problem?
I am in fact pleased to read this weblog posts which consists of tons of valuable information, thanks for providing such statistics.
It’s not my first time to visit this web site, i am browsing this web page dailly and get nice facts from here
every day.
Nice blog here! Also your site loads up 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
I loved as much as you’ll receive carried out right here.
The sketch is attractive, your authored material stylish.
nonetheless, you command get bought an shakiness over that you wish be delivering the following.
unwell unquestionably come more formerly
again since exactly the same nearly a lot often inside
case you shield this increase.
Fantastic site you have here but I was wanting to know if you knew of any
discussion boards that cover the same topics discussed
here? I’d really like to be a part of group where I
can get comments from other knowledgeable people that share the same interest.
If you have any recommendations, please let me know. Appreciate it!
Hi everyone, it’s my first pay a visit at this website, and post is in fact
fruitful for me, keep up posting these content.
Pretty! This has been a really wonderful post. Thank you for providing these details.
We absolutely love your blog and find most of your post’s to
be exactly what I’m looking for. Would you offer guest writers
to write content to suit your needs? I wouldn’t
mind composing a post or elaborating on some of the subjects you write regarding here.
Again, awesome site!
I’m not that much of a online reader to be honest but your blogs really nice, keep it up!
I’ll go ahead and bookmark your website to come back later on.
Many thanks
I’ve been surfing online more than three hours as of
late, yet I by no means found any interesting article like yours.
It is beautiful worth enough for me. Personally, if all website owners and bloggers
made good content material as you probably did, the net
will likely be much more helpful than ever before.
I’m often to running a blog and i really respect your content. The article has really peaks my interest. I’m going to bookmark your website and hold checking for brand spanking new information.
Great blog! I am loving it!! Will come back again. I am bookmarking your feeds also.
This post is worth everyone’s attention. Where can I find out more?
I like this web site its a master peace ! Glad I discovered this on google .
An interesting discussion is worth comment. I think that you should write more on this topic, it might not be a taboo subject but generally people are not enough to speak on such topics. To the next. Cheers
My relatives always say that I am wasting my time here at net,
however I know I am getting know-how every day by reading such nice content.
wow, awesome post.Much thanks again. Really Cool.
Saved as a favorite, I like your blog!
Very nice post. I just stumbled upon your blog and wanted to say that I’ve really enjoyed browsing your blog posts.
After all I’ll be subscribing to your feed and I hope you write again very
soon!
When some one searches for his necessary thing, thus he/she desires
to be available that in detail, therefore that thing is maintained over here.
I every time spent my half an hour to read this weblog’s content every day along with a cup of coffee.
What i don’t understood is if truth be told how you’re
not really much more neatly-favored than you might be now.
You are so intelligent. You realize therefore significantly
with regards to this subject, produced me personally imagine it from a lot
of numerous angles. Its like men and women don’t seem to be
involved unless it is something to accomplish with Girl
gaga! Your individual stuffs outstanding. Always take care of
it up!
Please let me know if you’re looking for a writer for your site.
You have some really great posts and I think I would be a good asset.
If you ever want to take some of the load off, I’d absolutely love to write some material for your
blog in exchange for a link back to mine. Please blast me an e-mail if interested.
Thank you!
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 waste your intelligence on just posting videos to your site when you could be giving us something informative to read?
Enjoyed every bit of your blog. Want more.
It’s hard to find educated people about this topic, however, you seem like you know what you’re talking
about! Thanks
Hmm it looks like your site ate my first comment (it was
extremely long) so I guess I’ll just sum it up what I submitted and
say, I’m thoroughly enjoying your blog. I too am an aspiring blog writer but I’m still new to everything.
Do you have any points for beginner blog writers? I’d really appreciate it.
Very good info. Lucky me I found your site by accident
(stumbleupon). I have saved it for later!
Thanks for sharing, this is a fantastic post. Cool.
Woah! I’m really digging the template/theme of this website.
It’s simple, yet effective. A lot of times it’s very difficult to get that “perfect balance” between superb usability and visual appeal.
I must say you have done a awesome job with this.
In addition, the blog loads extremely fast for
me on Chrome. Superb Blog!
Everyone loves it when people come together and share opinions.
Great website, stick with it!
Amazing! This blog looks just like my old one! It’s on a completely different topic but it
has pretty much the same page layout and design. Superb choice of colors!
Wow, marvelous blog structure! How lengthy have you ever been running a blog for?
you made running a blog look easy. The whole glance of your website
is magnificent, as neatly as the content material!
Wow, this article is nice, my younger sister is analyzing these kinds of things, thus I am going to let know her.
I really liked your blog.Thanks Again. Cool.
It is really a great and helpful piece of information. I am satisfied that you shared this helpful info with us.
Please stay us up to date like this. Thanks for sharing.
I just like the valuable info you supply on your articles.
I will bookmark your weblog and take a look at
once more here frequently. I’m relatively sure I’ll learn lots of new
stuff right right here! Best of luck for the next!
Normally I do not read article on blogs, but I wish to say that this write-up very forced me to try and do it!
Your writing taste has been amazed me. Thank you, very nice article.
Write more, thats all I have to say. Literally, it seems
as though you relied on the video to make your point.
You definitely know what youre talking about, why throw away your intelligence on just posting videos to your site
when you could be giving us something informative to read?
Thanks so much for the article. Keep writing.
Hello, for all time i used to check weblog posts here in the early
hours in the dawn, for the reason that i like to learn more
and more.
WOW just what I was searching for. Came here by searching
for ps4 games
Excellent blog here! Also your site so much up fast!
What web host are you the use of? Can I am getting your associate
hyperlink to your host? I desire my web site loaded up as fast as yours lol
I will right away take hold of your rss as I can’t in finding your email subscription link or e-newsletter service.
Do you have any? Please let me recognize so that I may subscribe.
Thanks.
Greetings! This is my first visit to your blog!
We are a group of volunteers and starting a new initiative in a community
in the same niche. Your blog provided us valuable information to work on. You
have done a marvellous job!
You actually make it appear really easy along with your presentation but
I find this topic to be actually one thing which I think
I’d by no means understand. It sort of feels too complicated and very extensive for me.
I’m having a look ahead on your subsequent put up, I’ll try to get
the hang of it!
I am so grateful for your blog.Much thanks again. Want more.
I simply could not depart your web site prior to suggesting that I extremely enjoyed the standard info a person provide to your guests? Is gonna be back often in order to investigate cross-check new posts
Say, you got a nice article.Really looking forward to read more. Fantastic.
Very quickly this web site will be famous among all blog visitors,
due to it’s pleasant articles or reviews
I really liked your blog post.Really thank you! Keep writing.
Wow that was unusual. I just wrote an incredibly long comment but
after I clicked submit my comment didn’t show up.
Grrrr… well I’m not writing all that over again. Anyhow,
just wanted to say excellent blog!
Thank you for your article post.Really looking forward to read more. Great.
I loved your blog article.Much thanks again. Much obliged.
I really enjoy the blog article.Much thanks again. Fantastic.
I blog frequently and I genuinely appreciate your information. This great article has truly peaked my interest.
I will bookmark your website and keep checking for new details about
once a week. I subscribed to your Feed as well.
Thanks for sharing your thoughts about sling tv. Regards
I appreciate you sharing this blog post.Thanks Again. Keep writing.
This paragraph provides clear idea designed for the new people of
blogging, that really how to do blogging and site-building.
I think this is a real great blog post.Really thank you! Really Cool.
Fantastic beat ! I wish to apprentice whilst you amend your website, how could i
subscribe for a blog web site? The account helped me
a appropriate deal. I were tiny bit familiar of this your broadcast offered bright transparent concept
Im thankful for the article post.Really looking forward to read more. Really Cool.
Thank you ever so for you post.Really looking forward to read more. Will read on…
Say, you got a nice blog article.Thanks Again. Great.
A round of applause for your article. Much obliged.
Thank you ever so for you blog post.Much thanks again. Keep writing.
Hey I am so thrilled I found your blog, I really found you by error, while I was
looking on Yahoo for something else, Nonetheless I am here now and would
just like to say thank you for a marvelous post and a
all round interesting blog (I also love the theme/design),
I don’t have time to read it all at the minute but I have bookmarked it and also
added your RSS feeds, so when I have time I will be back to
read much more, Please do keep up the great job.
Really enjoyed this post. Awesome.
Im obliged for the blog.Much thanks again. Want more.
Pretty! This has been an incredibly wonderful post.
Many thanks for supplying these details.
The following time I read a weblog, I hope that it doesnt disappoint me as much as this one. I mean, I know it was my option to read, however I truly thought youd have something interesting to say. All I hear is a bunch of whining about something that you could possibly fix if you happen to werent too busy searching for attention.
I cannot thank you enough for the blog.Much thanks again. Want more.
Thanks for sharing your thoughts on sling tv. Regards
Very good article post.
Great, thanks for sharing this post.Really looking forward to read more. Much obliged.
Thanks again for the blog post.Thanks Again. Will read on…
I really liked your post.Really thank you! Awesome.
wow, awesome post.Really thank you!
I was able to find good advice from your blog articles.
Major thankies for the post.Thanks Again. Fantastic.
I am so grateful for your article post.Much thanks again. Really Great.
Im thankful for the blog post.Really looking forward to read more. Much obliged.
Major thanks for the blog post.Really thank you! Awesome.
Excellent post. I was checking constantly this weblog and I am inspired!
Extremely useful information particularly the final
phase 🙂 I care for such information a lot. I used to be looking for
this particular info for a very long time. Thank you and best of luck.
A round of applause for your blog article.Really looking forward to read more. Really Great.
Im thankful for the blog post. Awesome.
I am not sure where you’re getting your info,
but great topic. I needs to spend some time learning much more or understanding more.
Thanks for fantastic info I was looking for this info for my mission.
Thank you for your blog.Thanks Again. Will read on…
Im thankful for the blog article.Really looking forward to read more. Really Great.
Really informative blog post.Much thanks again. Great.
I really like and appreciate your post.Thanks Again. Really Great.
Im grateful for the blog.Really looking forward to read more. Much obliged.
It’s an awesome post for all the web users; they will take benefit from it I am sure.|
Hi there, its good article regarding media print, we all understand media is a enormous source of data.|
Really informative blog.Thanks Again. Fantastic.
Fine way of describing, and fastidious paragraph to take facts about my presentation subject, which i am going to present in college.|
Hello there, just became aware of your blog through Google, and found that it’s truly informative. I’m going to watch out for brussels. I’ll be grateful if you continue this in future. Numerous people will be benefited from your writing. Cheers!|
Hello there, You’ve done a great job. I will definitely digg it and in my view recommend to my friends. I am confident they will be benefited from this web site.|
Thanks for the blog post.Much thanks again. Really Cool.
Thank you ever so for you post.Thanks Again. Great.
I am curious to find out what blog system you have been working with? I’m having some small security issues with my latest site and I’d like to find something more risk-free. Do you have any solutions?|
Great, thanks for sharing this article post.Really thank you! Cool.
I truly appreciate this post. Fantastic.
Good day! This is my first visit to your blog! We are a team of volunteers and starting a new initiative in a community in the same niche. Your blog provided us valuable information to work on. You have done a outstanding job!|
Your style is unique compared to other people I’ve read stuff from. Many thanks for posting when you’ve got the opportunity, Guess I will just bookmark this site.|
wow, awesome blog post. Much obliged.
Hi everyone, it’s my first pay a visit at this website, and article is truly fruitful in support of me, keep up posting such articles or reviews.|
Wow, great article post. Awesome.
I’m curious to find out what blog platform you have been using? I’m experiencing some small security issues with my latest blog and I would like to find something more secure. Do you have any suggestions?|
Why viewers still make use of to read news papers when in this technological world the whole thing is existing on net?|
Very neat article.Much thanks again. Much obliged.
Thank you for your blog post. Cool.
You’ve made some really good points there. I looked on the web for additional information about the issue and found most people will go along with your views on this website.|
Excellent post! We will be linking to this particularly great post on our website. Keep up the great writing.|
Great article post.Really looking forward to read more. Want more.
Very good blog post.Much thanks again. Cool.
I’ve been browsing online more than three hours these days, but I by no means discovered any interesting article like yours. It’s lovely worth enough for me. Personally, if all website owners and bloggers made excellent content material as you did, the web will be a lot more useful than ever before.|
Very neat article post.Really thank you! Cool.
Great post. Keep writing.
I just couldn’t depart your site prior to suggesting that I really loved the usual information a person supply for your guests? Is gonna be back continuously to investigate cross-check new posts|
I just couldn’t leave your website prior to suggesting that I really enjoyed the standard info an individual supply to your guests? Is going to be again steadily to check out new posts|
We’re a gaggle of volunteers and starting a new scheme in our community. Your website offered us with helpful info to work on. You have performed a formidable activity and our entire group might be thankful to you.|