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


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