【LG3703】[SDOI2017]树点涂色

题面

洛谷

题解

更博辣，更博辣！！！

猪年的第一篇博客

一次只能染根到\(x\)，且染的颜色未出现过

这句话是我们解题的关键。

设\(x\)到根的颜色数为\(f(x)\)，则\(u\)到\(v\)的颜色数：\(f(u)+f(v)-f(lca_{u,v})+1\)

想一想，为什么？

很显然，如果没有\(1\)操作，我们直接树剖维护一下就可以了。

但是现在有了\(1\)操作。。。

这个\(1\)操作，其实是拉一条从\(x\)到根的链，染成一种颜色

这是不是很像\(LCT\)的\(access\)呢？

这样的话，我们就搞一颗\(LCT\)，\(access\)时，

因为每断一颗子树，那棵子树内必然要多加一个颜色段就是一个子树加，

每连上一颗子树，那棵子树内必然重复一个颜色段就是一个子树减。

那么我们用树剖维护每个点的\(f(x)\)

并魔改一下\(access\)即可

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = getchar();

    if (ch == '-') w = -1, ch = getchar();

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

    return w * data;

}

const int MAX_N = 1e5 + 5;

struct Graph { int to, next; } e[MAX_N << 1]; int fir[MAX_N], e_cnt;

void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; }

void Add_Edge(int u, int v) { e[e_cnt] = (Graph){v, fir[u]}, fir[u] = e_cnt++; }

int N, M;

int dfn[MAX_N], L[MAX_N], R[MAX_N], top[MAX_N];

int dep[MAX_N], fa[MAX_N], son[MAX_N], size[MAX_N], tim;

void dfs1(int x) {

	dep[x] = dep[fa[x]] + 1, size[x] = 1;

	for (int i = fir[x]; ~i; i = e[i].next) {

		int v = e[i].to; if (v == fa[x]) continue;

		fa[v] = x; dfs1(v); size[x] += size[v];

		if (size[son[x]] < size[v]) son[x] = v;

	}

}

void dfs2(int x, int tp) {

	top[x] = tp, L[x] = ++tim, dfn[tim] = x;

	if (son[x]) dfs2(son[x], tp);

	for (int i = fir[x]; ~i; i = e[i].next) {

		int v = e[i].to; if (v == fa[x] || v == son[x]) continue;

		dfs2(v, v);

	}

	R[x] = tim;

}

int LCA(int x, int y) {

	while (top[x] != top[y]) {

		if (dep[top[x]] < dep[top[y]]) swap(x, y);

		x = fa[top[x]];

	}

	return dep[x] < dep[y] ? x : y;

}

#define lson (o << 1)

#define rson (o << 1 | 1)

int val[MAX_N << 2], tag[MAX_N << 2];

void pushup(int o) { val[o] = max(val[lson], val[rson]); }

void puttag(int o, int v) { tag[o] += v; val[o] += v; }

void pushdown(int o, int l, int r) {

	if (l == r || !tag[o]) return ;

	puttag(lson, tag[o]);

	puttag(rson, tag[o]);

	tag[o] = 0;

}

void build(int o, int l, int r) {

	if (l == r) return (void)(val[o] = dep[dfn[l]]);

	int mid = (l + r) >> 1;

	build(lson, l, mid), build(rson, mid + 1, r);

	pushup(o);

}

void modify(int o, int l, int r, int ql, int qr, int v) {

	if (ql <= l && r <= qr) return (void)(puttag(o, v));

	pushdown(o, l, r);

	int mid = (l + r) >> 1;

	if (ql <= mid) modify(lson, l, mid, ql, qr, v);

	if (qr > mid) modify(rson, mid + 1, r, ql, qr, v);

	pushup(o);

}

int query(int o, int l, int r, int ql, int qr) {

	pushdown(o, l, r);

	if (ql <= l && r <= qr) return val[o];

	int mid = (l + r) >> 1, res = 0;

	if (ql <= mid) res = max(res, query(lson, l, mid, ql, qr));

	if (qr > mid) res = max(res, query(rson, mid + 1, r, ql, qr));

	return res;

} 

struct Node { int ch[2], fa; bool rev; } t[MAX_N];

bool get(int x) { return t[t[x].fa].ch[1] == x; }

bool nroot(int x) { return t[t[x].fa].ch[0] == x || t[t[x].fa].ch[1] == x; }

void rotate(int x) {

	int y = t[x].fa, z = t[y].fa, k = get(x);

	if (nroot(y)) t[z].ch[get(y)] = x;

	t[x].fa = z;

	t[t[x].ch[k ^ 1]].fa = y, t[y].ch[k] = t[x].ch[k ^ 1];

	t[y].fa = x, t[x].ch[k ^ 1] = y;

}

void splay(int x) {

	while (nroot(x)) {

		int y = t[x].fa;

		if (nroot(y)) get(x) ^ get(y) ? rotate(x) : rotate(y);

		rotate(x);

	}

}

int findroot(int x) { while (t[x].ch[0]) x = t[x].ch[0]; return x; }

void access(int x) {

	for (int y = 0; x; y = x, x = t[x].fa) {

		splay(x);

		if (t[x].ch[1]) {

			int rt = findroot(t[x].ch[1]);

			modify(1, 1, N, L[rt], R[rt], 1);

		}

		t[x].ch[1] = y;

		if (t[x].ch[1]) {

			int rt = findroot(t[x].ch[1]);

			modify(1, 1, N, L[rt], R[rt], -1);

		}

	}

} 

int main () {

	clearGraph();

	N = gi(), M = gi();

	for (int i = 1; i < N; i++) {

		int u = gi(), v = gi();

		Add_Edge(u, v);

		Add_Edge(v, u);

	}

	dfs1(1), dfs2(1, 1);

	for (int x = 2; x <= N; x++) t[x].fa = fa[x];

	build(1, 1, N);

	while (M--) {

		int op = gi();

		if (op == 1) access(gi());

		if (op == 2) {

			int u = gi(), v = gi(), lca = LCA(u, v);

			printf("%d\n", query(1, 1, N, L[u], L[u]) + query(1, 1, N, L[v], L[v])

				- 2 * query(1, 1, N, L[lca], L[lca]) + 1);

		}

		if (op == 3) {

			int x = gi();

			printf("%d\n", query(1, 1, N, L[x], R[x]));

		}

	}

	return 0;

}