[SDOI2017]树点涂色

洛谷 [SDOI2017]树点涂色

题目描述

Bob 有一棵 n n n 个点的有根树，其中 1 1 1 号点是根节点。Bob 在每个点上涂了颜色，并且每个点上的颜色不同。

定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。

Bob可能会进行这几种操作：

• 1 x 表示把点 x x x 到根节点的路径上所有的点染上一种没有用过的新颜色。

• 2 x y 求 x x x 到 y y y 的路径的权值。

• 3 x 在以 x x x 为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob一共会进行 m m m 次操作

数据范围

$1\leq n \leq 10^5，1\leq m \leq 10^5 $

题解报告

我们定义每个点的权值 v a l [ i ] val[i] val[i] 为， i i i 点到根节点路径的权值。

由操作 1 1 1，我们可以以 LCT 的 A c c e s s Access Access 操作为模型来实现操作1，具体来说就是， v a l [ i ] val[i] val[i] 等于第 i i i 个点到跟节点的虚链个数 + 1 +1 +1，每棵 S p l a y Splay Splay 树维护的是具有相同颜色的节点的集合。初始状态下每个节点代表一颗 S p l a y Splay Splay， v a l [ i ] = d e p [ i ] val[i] = dep[i] val[i]=dep[i]。

由树上差分的思想，可以得到 v a l ( i , j ) = v a l [ i ] + v a l [ j ] − 2 ∗ v a l [ L C A ( i , j ) ] + 1 val (i, j) = val[i] + val[j] - 2 * val[LCA (i, j)] + 1 val(i,j)=val[i]+val[j]−2∗val[LCA(i,j)]+1，(注意这里是在把路径权值转换成路径上虚链个数的前提下才成立的) 。

对于操作三，若按照 d f n dfn dfn 序建一棵线段树，则问题转化为求区间内最大值。

维护 v a l [ i ] val[i] val[i] 数组： A c c e s s Access Access 操作时，每次虚实链转变时，要分别找到虚实链的端点 ( S p l a y Splay Splay 树里一直跳左儿子即可)，对子树内的 v a l [ i ] val[i] val[i] 均加一或减一。

AC代码：

#include <bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int maxn = 1e5 + 5;

int n, m, tot;
int fa1[maxn], fa2[maxn], siz[maxn], son[maxn], dep[maxn];
int top[maxn], dfn[maxn], rk[maxn], bot[maxn];
int mx[maxn << 2], ls[maxn << 2], rs[maxn << 2], lazy[maxn << 2];
int ch[maxn][2];
vector <int> adj[maxn];

void dfs1 (int f, int u, int d) {
	fa1[u] = f, siz[u] = 1, dep[u] = d;
	for (auto it : adj[u]) {
		if (it == f) continue;
		dfs1 (u, it, d + 1);
		siz[u] += siz[it];
		if (siz[it] > siz[son[u]]) son[u] = it;
	}
}

int dfs2 (int f, int u, int tp) {
	top[u] = tp;
	dfn[u] = ++tot, rk[tot] = u, bot[u] = tot;
	if (son[u]) bot[u] = max (bot[u], dfs2 (u, son[u], tp));
	for (auto it : adj[u]) {
		if (it == f || it == son[u]) continue;
		bot[u] = max (bot[u], dfs2 (u, it, it));
	}
	return bot[u];
}

int lca (int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap (x, y);
		x = fa1[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}

void update (int cnt) {mx[cnt] = max (mx[ls[cnt]], mx[rs[cnt]]);}

void build (int cnt, int l, int r) {
	if (l == r) {
		mx[cnt] = dep[rk[l]];
		lazy[cnt] = 0;
		return;
	}
	int mid = l + r >> 1;
	build (ls[cnt] = ++tot, l, mid);
	build (rs[cnt] = ++tot, mid + 1, r);
	update (cnt);
}

void pushdown (int cnt) {
	mx[ls[cnt]] += lazy[cnt];
	mx[rs[cnt]] += lazy[cnt];
	
	lazy[ls[cnt]] += lazy[cnt];
	lazy[rs[cnt]] += lazy[cnt];	
	
	lazy[cnt] = 0;
}

void add (int cnt, int l, int r, int ql, int qr, int k) {
	if (l >= ql && r <= qr) {
		lazy[cnt] += k;
		mx[cnt] += k;
		return;
	}
	pushdown (cnt);
	int mid = l + r >> 1;
	if (ql <= mid) add (ls[cnt], l, mid, ql, qr, k);
	if (qr > mid) add (rs[cnt], mid + 1, r, ql, qr, k);
	update (cnt);
}

int query (int cnt, int l, int r, int ql, int qr) {
	if (l >= ql && r <= qr) return mx[cnt];
	pushdown (cnt);
	int mid = l + r >> 1;
	int res = -1;
	if (ql <= mid) res = max (res, query (ls[cnt], l, mid, ql, qr));
	if (qr > mid) res = max (res, query (rs[cnt], mid + 1, r, ql, qr));
	return res;
}

namespace LCT {
	bool Get (int x) {return x == ch[fa2[x]][1];}
	bool isRoot (int x) {return x != ch[fa2[x]][0] && x != ch[fa2[x]][1];}
	
	void Rotate (int x) {
		int y = fa2[x], z = fa2[y], chk = Get (x);
		if (!isRoot (y)) ch[z][Get (y)] = x;
		if (ch[x][chk ^ 1]) fa2[ch[x][chk ^ 1]] = y;
		ch[y][chk] = ch[x][chk ^ 1];
		ch[x][chk ^ 1] = y;
		fa2[y] = x, fa2[x] = z;
	}
	
	void Splay (int x) {
		for (int f = fa2[x]; f = fa2[x], !isRoot (x); Rotate (x)) {
			if (!isRoot (f)) Rotate (Get (f) == Get (x) ? f : x);
		}
	}
	
	int findRoot (int x) {
		while (ch[x][0]) x = ch[x][0];
		return x;
	}
	
	int Access (int x) {
		int last, tmp;
		for (last = 0; x; last = x, x = fa2[x]) {
			Splay (x);
			if (ch[x][1]) {
				tmp = findRoot (ch[x][1]);
				add (0, 1, n, dfn[tmp], bot[tmp], 1);
			}
			if (last) {
				tmp = findRoot (last);
				add (0, 1, n, dfn[tmp], bot[tmp], -1);
			}
			ch[x][1] = last;
		}
		return last;
	}
	
}

void init () {}

void charming () {
	init ();
	cin >> n >> m;
	for (int i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		adj[u].emplace_back (v);
		adj[v].emplace_back (u);
	}
	dfs1 (0, 1, 1);
	dfs2 (0, 1, 1);
	tot = 0;
	build (0, 1, n);
	for (int i = 1; i <= n; ++i) fa2[i] = fa1[i];
	int opt, x, y, LCA, val1, val2, val3;
	for (int i = 1; i <= m; ++i) {
		cin >> opt >> x;
		if (opt == 1) LCT :: Access (x);
		else if (opt == 2) {
			cin >> y;
			LCA = lca (x, y);
			val1 = query (0, 1, n, dfn[x], dfn[x]);
			val2 = query (0, 1, n, dfn[y], dfn[y]);
			val3 = query (0, 1, n, dfn[LCA], dfn[LCA]);
			cout << val1 + val2 - (val3 << 1) + 1 << endl;
		}
		else cout << query (0, 1, n, dfn[x], bot[x]) << endl;
	}
}

signed main () {
	charming ();
	return 0;
}

收获&总结

L C T LCT LCT 建模也很重要，这次算是见识到一种方法了。

另外本题不能使用 S p l i t Split Split 操作，因为会换根，导致我们 S p l a y Splay Splay 维护同一种颜色的点的集合的性质就被破坏了。

所以这道题 L C T LCT LCT 只能通过 A c c e s s Access Access 操作起建模作用。