# 【BZOJ 4817】[SDOI2017] 树点涂色

### 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];

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;
}

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;

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() {
for (int i = 1; i < n; i++) {
}
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++) {
if (opt == 1) {
} else if (opt == 2) {
printf("%d\n", SGT.query(in[u]) + SGT.query(in[v]) - 2 * SGT.query(in[lca]) + 1);
} else {
printf("%d\n", SGT.query(in[x], ot[x]));
}
}
return 0;
}


## 84 thoughts to “【BZOJ 4817】[SDOI2017] 树点涂色”

1. 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.

2. 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!

3. 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.

4. Very good post! We are linking to this particularly great content on our
site. Keep up the great writing.

5. WOW just what I was searching for. Came here by searching for gamefly free trial

6. 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!

7. 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

8. 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!

9. Pretty! This was a really wonderful post. Many thanks for supplying this information.

10. Quality content is the crucial to interest the users to go to see the web page, that’s what this
web page is providing.

11. 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!

12. 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!

13. 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

14. 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.

15. Hello There. I found your weblog the usage of msn. That is a really
smartly written article. I’ll make sure to bookmark it
the post. I will certainly comeback.

16. Hi to every one, the contents present at this web page
are genuinely amazing for people knowledge, well, keep up the good work fellows.

17. For most recent information you have to pay a quick visit internet and on the web I found this web site as a best

18. This is a topic that is near to my heart… Cheers! Where are

19. 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.

20. 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?

21. 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.

22. Your method of describing all in this paragraph is truly pleasant,
all be able to effortlessly be aware of it, Thanks a
lot.

23. 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!

24. 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.

25. 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

26. 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.

27. 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

28. 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.

29. 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

30. 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

31. Paragraph writing is also a excitement, if you be familiar with afterward you
can write if not it is complex to write.

32. I think this is one of the most important info for me.
The site style is wonderful, the articles is really excellent :
D. Good job, cheers

33. 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?

34. Thanks very nice blog!

35. 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

36. 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!

37. 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

38. 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.

39. 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?

40. I am in fact pleased to read this weblog posts which consists of tons of valuable information, thanks for providing such statistics.

41. 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.

to your host? I wish my web site loaded up as quickly as yours lol

43. 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.

44. 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!

45. 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.

46. Pretty! This has been a really wonderful post. Thank you for providing these details.

47. 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!

48. 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

49. 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.

50. 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.

51. Great blog! I am loving it!! Will come back again. I am bookmarking your feeds also.

52. This post is worth everyone’s attention. Where can I find out more?

53. I like this web site its a master peace ! Glad I discovered this on google .

54. 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

55. 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.

56. wow, awesome post.Much thanks again. Really Cool.

57. Saved as a favorite, I like your blog!

58. 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!

59. 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.

60. I every time spent my half an hour to read this weblog’s content every day along with a cup of coffee.

61. 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!

62. 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

Thank you!

63. 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?

64. Enjoyed every bit of your blog. Want more.

65. It’s hard to find educated people about this topic, however, you seem like you know what you’re talking

66. 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.

67. Very good info. Lucky me I found your site by accident
(stumbleupon). I have saved it for later!

68. Thanks for sharing, this is a fantastic post. Cool.

69. 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.
me on Chrome. Superb Blog!

70. Everyone loves it when people come together and share opinions.

Great website, stick with it!

71. 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!

72. 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!

74. I really liked your blog.Thanks Again. Cool.

75. 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.

76. 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!

77. 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.

78. 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?

79. 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.

80. WOW just what I was searching for. Came here by searching
for ps4 games

81. Excellent blog here! Also your site so much up fast!
What web host are you the use of? Can I am getting your associate