自动搬运

查看原文

来自洛谷，原作者为

	Caii **

搬运于2025-08-24 21:51:47，当前版本为作者最后更新于2018-03-28 10:07:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

怎么题解全是LCT，我树剖不服

第一个操作就是树链覆盖，放到序列上就是区间合并，区间合并暴力的时间复杂度是均摊 $O(1)$ 的(不考虑在其他数据结构上的时间消耗)，于是一个显然的思路就是第一个操作暴力搞，每次在重链上找到一段相同的颜色，暴力在线段树上修改，时间复杂度均摊是 $O(\log N)$ 的

线段树上维护一个节点到根节点的权值 $v$

那么第二个操作就是 $v_x+v_y-2v_{LCA(x, y)}+1$

第三个操作线段树区间最值

没了

时间复杂度:$O(N\log^2N)$

#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define DEBUG(args...) fprintf(stderr, args)

typedef long long LL;

#define FOR(i, l, r) for(int i = (l), i##_end = (r); i <= i##_end; ++i)
#define REP(i, l, r) for(int i = (l), i##_end = (r); i <  i##_end; ++i)
#define DFR(i, l, r) for(int i = (l), i##_end = (r); i >= i##_end; --i)
#define DRP(i, l, r) for(int i = (l), i##_end = (r); i >  i##_end; --i)

template<class T>T Min(const T &a, const T &b) {return a < b ? a : b;}
template<class T>T Max(const T &a, const T &b) {return a > b ? a : b;}
template<class T>bool Chkmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T>bool Chkmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

class fast_input {
private:
	static const int SIZE = 1 << 15 | 1;
	char buf[SIZE], *front, *back;

	void Next(char &c) {
	    if(front == back) back = (front = buf) + fread(buf, 1, SIZE, stdin);
		c = front == back ? (char)EOF : *front++;
	}

public :
	template<class T>void operator () (T &x) {
		char c, f = 1;
		for(Next(c); !isdigit(c); Next(c)) if(c == '-') f = -1;
		for(x = 0; isdigit(c); Next(c)) x = x * 10 + c - '0';
		x *= f;
	}
	void operator () (char &c, char l = 'a', char r = 'z') {
		for(Next(c); c > r || c < l; Next(c)) ;
	}
}input;

const int SN = 100000 + 47;
const int ST = SN << 2 | 1;
const int SE = 200000 + 47;
const int SM = 200000 + 47;

int head[SN], nxt[SE], to[SE];
int col_top[SM], col_bot[SM], col_now;
int size[SN], son[SN], fa[SN], deep[SN];
int top[SN], f[SN], g[SN], h[SN], rank;
int max[ST], tag[ST], col[ST];
int n;

void Add(int, int);
void DFS(int);
void DFS(int, int);
void Build(int, int, int);
void Update(int);
void Modify(int, int, int, int, int, int);
void PushAdd(int, int);
void PushDown(int);
int Ask(int, int, int, int, int);
void ModifyCol(int, int, int, int, int, int);
int AskCol(int, int, int, int);
void Modify(int, int);
int Ask0(int, int);
int Ask1(int);

int __lp, __lq;
int LCA(int, int);

int main() {

#ifdef Cai
	freopen("s.in", "r", stdin);
#endif

	int m, x, y, z;
	
	input(n), input(m);
	FOR(i, 2, n) input(x), input(y), Add(x, y);

	col_now = n;
	FOR(i, 1, n) col_top[i] = col_bot[i] = i;

	deep[1] = 1, DFS(1), DFS(1, -1), Build(1, 1, n);

	while(m--) {
		//DEBUG("[%d]\n", m);
		input(x), input(y);
		if(x == 1) Modify(y, ++col_now);
		else if(x == 2) input(z), printf("%d\n", Ask0(y, z));
		else printf("%d\n", Ask1(y));
	}

	return 0;

}

void Add(int x, int y) {
	static int _ = 0;
	nxt[++_] = head[x], head[x] = _, to[_] = y;
	nxt[++_] = head[y], head[y] = _, to[_] = x;
}

void DFS(int x) {
	size[x] = 1;
	for(int i = head[x]; i; i = nxt[i])
		if(to[i] != fa[x]) {
			fa[to[i]] = x, deep[to[i]] = deep[x] + 1;
			DFS(to[i]), size[x] += size[to[i]];
			if(size[to[i]] > size[son[x]]) son[x] = to[i];
		}
}

void DFS(int x, int y) {
	top[x] = y, f[x] = ++rank, h[rank] = x;
	if(son[x]) DFS(son[x], y);
	for(int i = head[x]; i; i = nxt[i])
		if(to[i] != fa[x] && to[i] != son[x])
			DFS(to[i], to[i]);
	g[x] = rank;
}

void Build(int rt, int l, int r) {
	if(l == r) {max[rt] = deep[h[l]], tag[rt] = 0, col[rt] = h[l]; return ;}
	int mid = l + r >> 1;
	Build(rt << 1, l, mid), Build(rt << 1 | 1, mid + 1, r);
	Update(rt);
}

void Update(int rt) {
	max[rt] = Max(max[rt << 1], max[rt << 1 | 1]);
}

void Modify(int rt, int l, int r, int s, int t, int k) {
	if(l == s && r == t) {PushAdd(rt, k); return ;}
	PushDown(rt);
	int mid = l + r >> 1;
	if(t <= mid)
		Modify(rt << 1, l, mid, s, t, k);
	else if(s > mid)
		Modify(rt << 1 | 1, mid + 1, r, s, t, k);
	else {
		Modify(rt << 1, l, mid, s, mid, k);
		Modify(rt << 1 | 1, mid + 1, r, mid + 1, t, k);
	}
	Update(rt);
}

void PushAdd(int rt, int x) {
	tag[rt] += x, max[rt] += x;
}

void PushDown(int rt) {
	if(tag[rt]) PushAdd(rt << 1, tag[rt]), PushAdd(rt << 1 | 1, tag[rt]);
	tag[rt] = 0;
}

int Ask(int rt, int l, int r, int s, int t) {
	if(l == s && r == t) return max[rt];
	PushDown(rt);
	int mid = l + r >> 1;
	if(t <= mid)
		return Ask(rt << 1, l, mid, s, t);
	else if(s > mid)
		return Ask(rt << 1 | 1, mid + 1, r, s, t);
	else
		return Max(Ask(rt << 1, l, mid, s, mid),
				   Ask(rt << 1 | 1, mid + 1, r, mid + 1, t));
}

void ModifyCol(int rt, int l, int r, int s, int t, int k) {
	if(l == s && r == t) {col[rt] = k; return ;}
	int mid = l + r >> 1;
	if(t <= mid)
		ModifyCol(rt << 1, l, mid, s, t, k);
	else if(s > mid)
		ModifyCol(rt << 1 | 1, mid + 1, r, s, t, k);
	else {
		ModifyCol(rt << 1, l, mid, s, mid, k);
		ModifyCol(rt << 1 | 1, mid + 1, r, mid + 1, t, k);
	}
}

int AskCol(int rt, int l, int r, int p) {
	if(l == r) return col[rt];
	int mid = l + r >> 1;
	if(p <= mid) return Max(col[rt], AskCol(rt << 1, l, mid, p));
	else return Max(col[rt], AskCol(rt << 1 | 1, mid + 1, r, p));
}

void Modify(int x, int y) {
	col_bot[y] = x, col_top[y] = 1;
	int p, q, r, c, nl = 0, nr = 0, toplastc, nextx;
	while(x) {
		p = Ask(1, 1, n, f[x], f[x]);
		c = AskCol(1, 1, n, f[x]);
		r = col_top[c];
		if(f[r] < f[top[x]]) {
			ModifyCol(1, 1, n, f[top[x]], f[x], y);
			Modify(1, 1, n, f[top[x]], g[top[x]], 1 - p);
			if(nl) Modify(1, 1, n, nl, nr, p - 1);
		}
		else {
			ModifyCol(1, 1, n, f[r], f[x], y);
			Modify(1, 1, n, f[r], g[r], 1 - p);
			if(nl) Modify(1, 1, n, nl, nr, p - 1);
		}
		if(col_bot[c] != x) {
			LCA(col_bot[c], x); // __lp is a child of x, which col is c
			if(f[__lp] != nl) {
				Modify(1, 1, n, f[__lp], g[__lp], 1);
				toplastc = __lp;
			}
		}
		if(f[r] < f[top[x]]) 
			nl = f[top[x]], nr = g[top[x]], x = fa[top[x]];
		else
			nl = f[r], nr = g[r], x = fa[r], col_top[c] = toplastc;
	}
}

int Ask0(int x, int y) {
	int lca = LCA(x, y);
	int ans = Ask(1, 1, n, f[x], f[x]) + Ask(1, 1, n, f[y], f[y]);
	ans -= 2 * Ask(1, 1, n, f[lca], f[lca]);
	return ans + 1;
}

int Ask1(int x) {
	return Ask(1, 1, n, f[x], g[x]);
}

int LCA(int x, int y) {
	while(top[x] != top[y]) 
		if(deep[top[x]] > deep[top[y]]) __lp = top[x], x = fa[top[x]];
		else __lq = top[y], y = fa[top[y]];
	if(x == y) return x;
	if(deep[x] < deep[y]) return __lq = son[x], x;
	return __lp = son[y], y;
}

/*
g++ -o s s.cpp -O2; for((i = 1; i <= 10; ++i)) do cp paint$i.in s.in; ./s > s.out; diff paint$i.out s.out -w > s.res; echo $?; done
*/