@description@
Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路
径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：
1 x:把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y:求x到y的路径的权值。
3 x:在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。
Bob一共会进行m次操作。
Input
第一行两个数n,m。
接下来n-1行，每行两个数a,b，表示a与b之间有一条边。
接下来m行，表示操作，格式见题目描述
1<=n,m<=100000
Output
每当出现2,3操作，输出一行。
如果是2操作，输出一个数表示路径的权值
如果是3操作，输出一个数表示权值的最大值
Sample Input
5 6
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
Sample Output
3
4
2
2
@solution@
初看会觉得这道题十分难以下手：对于那个什么“把点x到根结点的路径上所有的点染上一种没有用过的新颜色”这个操作完全没有办法。
但如果仔细思考，外加你数据结构学得非常非常强，可以发现这个其实就是 link-cut-tree 中的 access 操作。
考虑点破了这一点后，我们该如何维护“点到根结点的路径权值（不同颜色段数量）”。
其实你发现，这个就 = 点到根结点经过的 link-cut-tree 中的轻边数量 + 1。
我们考虑在每一次 access 的时候，将所有轻边变重边，重边变轻边的地方作修改。而根据 link-cut-tree 的时间复杂度分析这个修改数量均摊 O(logn)。
实现上，我们可以将 “单边修改+到根的链查询” 变为 “子树修改+单点查询”，转为 dfs 序然后线段树维护。
对于询问 2 就只需要查询出 lca 然后变成 f(u) + f(v) - 2*f(lca)。
对于询问 3，将树转为 dfs 序后就在 dfs 序上查询最大值。
时间复杂度 O(nlog^2n），瓶颈卡在操作 1 的 access + 线段树上修改，其他两个询问每一次是 O(logn)。
@accepted code@
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
int dfn[MAXN + 5], tid[MAXN + 5], siz[MAXN + 5], dep[MAXN + 5], fa[20][MAXN + 5], dcnt = 0;
struct Segtree{
struct node{
int l, r;
int tg, mx;
}t[4*MAXN + 5];
void pushdown(int x) {
if( t[x].tg ) {
t[x<<1].tg += t[x].tg, t[x<<1].mx += t[x].tg;
t[x<<1|1].tg += t[x].tg, t[x<<1|1].mx += t[x].tg;
t[x].tg = 0;
}
}
void pushup(int x) {
t[x].mx = max(t[x<<1].mx, t[x<<1|1].mx);
}
void build(int x, int l, int r) {
t[x].l = l, t[x].r = r, t[x].tg = 0, t[x].mx = 0;
if( l == r ) {
t[x].mx = dep[dfn[l]] - 1;
return ;
}
int mid = (l + r) >> 1;
build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
pushup(x);
}
void modify(int x, int l, int r, int d) {
if( l > t[x].r || r < t[x].l )
return ;
if( l <= t[x].l && t[x].r <= r ) {
t[x].tg += d, t[x].mx += d;
return ;
}
pushdown(x);
modify(x << 1, l, r, d);
modify(x << 1 | 1, l, r, d);
pushup(x);
}
int query(int x, int l, int r) {
if( l > t[x].r || r < t[x].l )
return 0;
if( l <= t[x].l && t[x].r <= r )
return t[x].mx;
pushdown(x);
return max(query(x << 1, l, r), query(x << 1 | 1, l, r));
}
}T1;
struct Link_Cut_Tree{
struct node{node *ch[2], *fa;}pl[MAXN + 5], *NIL;
Link_Cut_Tree() {
NIL = &pl[0];
NIL->ch[0] = NIL->ch[1] = NIL->fa = NIL;
}
bool is_root(node *x) {
return x->fa->ch[0] != x && x->fa->ch[1] != x;
}
void set_child(node *x, node *y, int d) {
if( x != NIL ) x->ch[d] = y;
if( y != NIL ) y->fa = x;
}
void rotate(node *x) {
node *y = x->fa; int d = (y->ch[1] == x);
if( is_root(y) ) x->fa = y->fa;
else set_child(y->fa, x, (y->fa->ch[1] == y));
set_child(y, x->ch[!d], d);
set_child(x, y, !d);
}
void splay(node *x) {
while( !is_root(x) ) {
node *y = x->fa;
if( is_root(y) )
rotate(x);
else {
if( (y->fa->ch[1] == y) == (y->ch[1] == x) )
rotate(y);
else rotate(x);
rotate(x);
}
}
}
node *find(node *x) {
node *ret = x;
while( ret->ch[0] != NIL )
ret = ret->ch[0];
splay(ret);
return ret;
}
void access(node *x) {
node *y = NIL;
while( x != NIL ) {
splay(x);
node *k = x->ch[1];
x->ch[1] = y;
if( k != NIL ) {
k = find(k);
T1.modify(1, tid[k-pl], tid[k-pl]+siz[k-pl]-1, 1);
}
x = find(x);
if( x->fa != NIL )
T1.modify(1, tid[x-pl], tid[x-pl]+siz[x-pl]-1, -1);
y = x, x = x->fa;
}
}
}T2;
Link_Cut_Tree::node *nd[MAXN + 5];
struct edge{
edge *nxt; int to;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];
void addedge(int u, int v) {
edge *p = (++ecnt);
p->to = v, p->nxt = adj[u], adj[u] = p;
p = (++ecnt);
p->to = u, p->nxt = adj[v], adj[v] = p;
}
void dfs(int x, int f) {
dfn[++dcnt] = x, tid[x] = dcnt, dep[x] = dep[f] + 1, siz[x] = 1, fa[0][x] = f;
for(int i=1;i<20;i++)
fa[i][x] = fa[i-1][fa[i-1][x]];
for(edge *p=adj[x];p;p=p->nxt) {
if( p->to == f ) continue;
dfs(p->to, x); siz[x] += siz[p->to];
}
}
int lca(int u, int v) {
if( dep[u] < dep[v] ) swap(u, v);
for(int i=19;i>=0;i--)
if( dep[fa[i][u]] >= dep[v] )
u = fa[i][u];
if( u == v ) return u;
for(int i=19;i>=0;i--)
if( fa[i][u] != fa[i][v] )
u = fa[i][u], v = fa[i][v];
return fa[0][u];
}
int main() {
int n, m; scanf("%d%d", &n, &m);
for(int i=1;i<n;i++) {
int a, b; scanf("%d%d", &a, &b);
addedge(a, b);
}
for(int i=1;i<=n;i++)
nd[i] = &T2.pl[i], nd[i]->fa = nd[i]->ch[0] = nd[i]->ch[1] = T2.NIL;
dfs(1, 0);
for(int i=2;i<=n;i++)
nd[i]->fa = nd[fa[0][i]];
T1.build(1, 1, n);
for(int i=1;i<=m;i++) {
int op; scanf("%d", &op);
if( op == 1 ) {
int x; scanf("%d", &x);
T2.access(nd[x]);
}
else if( op == 2 ) {
int x, y; scanf("%d%d", &x, &y);
int l = lca(x, y);
printf("%d
", T1.query(1, tid[x], tid[x]) + T1.query(1, tid[y], tid[y]) - 2*T1.query(1, tid[l], tid[l]) + 1);
}
else {
int x; scanf("%d", &x);
printf("%d
", T1.query(1, tid[x], tid[x]+siz[x]-1) + 1);
}
}
}
@details@
感觉这个思想还是挺有意思的（虽然最近好像就莫名其妙变成了一种套路？）