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

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

发表评论

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