【BZOJ 4817】[SDOI2017] 树点涂色

相关链接

题目传送门: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;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注