树点涂色
Time Limit: 10 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]
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行，表示操作，格式见题目描述。
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
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
4
2
2
HINT
1<=n,m<=100000
Solution
我们将边两端的点颜色相同的边设为实边，不同的设为虚边。那么一次新增颜色的操作显然就是LCT的access操作！access的时候恰是虚边和实边的转换。
那么我们只要用线段树维护每个点到根的贡献，结合dfs序来实现子树加，每次在LCT进行access的时候进行+-1修改，然后询问的时候用区间求和，区间最值求得答案即可。
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long s64; const int ONE = 2e5+; int n,m;
int x,y,P;
int POS[ONE],POSCNT;
int pos[ONE],dfn_cnt,size[ONE],dfn[ONE];
int Dep[ONE],son[ONE],Top[ONE];
int lc[ONE],rc[ONE],fa[ONE],fat[ONE];
int res_max,res_value; inline int get()
{
int res=,Q=; char c;
while( (c=getchar())< || c>)
if(c=='-')Q=-;
if(Q) res=c-;
while((c=getchar())>= && c<=)
res=res*+c-;
return res*Q;
} namespace tree
{
int next[ONE],first[ONE],go[ONE],tot=; void Add(int u,int v)
{
next[++tot]=first[u]; first[u]=tot; go[tot]=v;
next[++tot]=first[v]; first[v]=tot; go[tot]=u;
} void Dfs(int u,int father)
{
pos[u] = ++dfn_cnt; dfn[dfn_cnt] = u;
size[u] = ;
Dep[u] = Dep[father] + ;
for(int e=first[u];e;e=next[e])
{
int v=go[e];
if(v==father) continue;
fa[v] = u; fat[v] = u;
Dfs(v,u);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
} void Dfs_twice(int u,int father)
{
POS[u] = ++POSCNT;
if(son[u])
{
int v=son[u];
Top[v] = Top[u];
Dfs_twice(v,u);
} for(int e=first[u];e;e=next[e])
{
int v=go[e];
if(v==father || v==son[u]) continue;
Top[v] = v;
Dfs_twice(v,u);
}
} int LCA(int x,int y)
{
while(Top[x]!=Top[y])
{
if( Dep[Top[x]] < Dep[Top[y]] ) swap(x,y);
x = fat[Top[x]];
}
if(POS[x] > POS[y]) swap(x,y);
return x;
}
} namespace Seg
{
struct power
{
int add,value;
int maxx;
}Node[ONE*]; void pushdown(int i,int Q)
{
if(Node[i].add)
{
Node[i<<].add += Node[i].add;
Node[i<<|].add += Node[i].add;
Node[i<<].maxx += Node[i].add;
Node[i<<|].maxx += Node[i].add;
Node[i<<].value += Node[i].add * (Q-Q/);
Node[i<<|].value += Node[i].add * (Q/);
Node[i].add = ;
}
} void Build(int i,int l,int r)
{
if(l==r)
{
Node[i].value = Dep[dfn[l]];
Node[i].maxx = Dep[dfn[l]];
return ;
}
int mid = l+r>>;
Build(i<<,l,mid); Build(i<<|,mid+,r);
Node[i].value = Node[i<<].value + Node[i<<|].value;
Node[i].maxx = max(Node[i<<].maxx, Node[i<<|].maxx);
} void Update(int i,int l,int r,int L,int R,int x)
{
if(L<=l && r<=R)
{
Node[i].add += x;
Node[i].value += (r-l+)*x;
Node[i].maxx += x;
return;
}
pushdown(i,r-l+);
int mid = l+r>>;
if(L<=mid) Update(i<<,l,mid,L,R,x);
if(mid+<=R) Update(i<<|,mid+,r,L,R,x); Node[i].value = Node[i<<].value + Node[i<<|].value;
Node[i].maxx = max(Node[i<<].maxx , Node[i<<|].maxx);
} void Query(int i,int l,int r,int L,int R)
{
if(L<=l && r<=R)
{
res_max = max(res_max,Node[i].maxx);
res_value += Node[i].value;
return;
}
pushdown(i,r-l+);
int mid = l+r>>;
if(L<=mid) Query(i<<,l,mid,L,R);
if(mid+<=R) Query(i<<|,mid+,r,L,R);
}
} namespace LCT
{
int is_real(int x)
{
return (lc[fa[x]]==x || rc[fa[x]]==x);
} void Turn(int x)
{
int y = fa[x], z = fa[y];
int b = x==lc[y] ? rc[x]:lc[x]; fa[x] = z; fa[y] = x;
if(b) fa[b] = y; if(z)
{
if(y == lc[z]) lc[z] = x;
else
if(y == rc[z]) rc[z] = x;
} if(x==lc[y]) rc[x]=y,lc[y]=b;
else lc[x]=y,rc[y]=b;
} void Splay(int x)
{
while(is_real(x))
{
if(is_real(fa[x]))
{
if( (lc[fa[x]]==x) == (lc[fa[fa[x]]]==fa[x])) Turn(fa[x]);
else Turn(x);
}
Turn(x);
}
} int find_root(int x)
{
while(lc[x]) x=lc[x];
return x;
} void access(int x)
{
for(int p=x,q=; p; q=p,p=fa[p])
{
Splay(p);
if(rc[p])
{
int N = find_root(rc[p]);
Seg::Update(,,n,pos[N],pos[N]+size[N]-,);
} rc[p] = q;
if(rc[p])
{
int N = find_root(rc[p]);
Seg::Update(,,n,pos[N],pos[N]+size[N]-,-);
}
}
}
} int Getsum(int x,int y)
{
int Ans, Sx, Sy, SLCA, LCA;
LCA = tree::LCA(x,y);
x=pos[x], y=pos[y], LCA=pos[LCA];
res_value = ; Seg::Query(,,n,x,x); Sx = res_value;
res_value = ; Seg::Query(,,n,y,y); Sy = res_value;
res_value = ; Seg::Query(,,n,LCA,LCA); SLCA = res_value;
return Sx+Sy-*SLCA+;
} int Getmax(int x)
{
res_max = ;
Seg::Query(,,n,pos[x],pos[x]+size[x]-);
return res_max;
} int main()
{
n=get(); m=get();
for(int i=;i<=n-;i++)
{
x=get(); y=get();
tree::Add(x,y);
} tree::Dfs(,);
Top[] = , tree::Dfs_twice(,);
Seg::Build(,,n); while(m--)
{
P = get(); x=get();
if(P==)
LCT::access(x);
if(P==)
y=get(), printf("%d\n",Getsum(x,y));
if(P==)
printf("%d\n",Getmax(x));
}
}