[SDOI2017] 树点涂色
题目描述
Bob 有一棵 \(n\) 个点的有根树，其中 \(1\) 号点是根节点。Bob 在每个点上涂了颜色，并且每个点上的颜色不同。
定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。
Bob可能会进行这几种操作：
-
1 x表示把点 \(x\) 到根节点的路径上所有的点染上一种没有用过的新颜色。 -
2 x y求 \(x\) 到 \(y\) 的路径的权值。 -
3 x在以 \(x\) 为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。
Bob一共会进行 \(m\) 次操作
输入格式
第一行两个数 \(n,m\)。
接下来 \(n-1\) 行，每行两个数 \(a,b\)，表示 \(a\) 与 \(b\) 之间有一条边。
接下来 \(m\) 行，表示操作，格式见题目描述
输出格式
每当出现 \(2,3\) 操作，输出一行。
如果是 \(2\) 操作，输出一个数表示路径的权值
如果是 \(3\) 操作，输出一个数表示权值的最大值
样例 #1
样例输入 #1
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
3
4
2
2
提示
共 \(10\) 个测试点。
测试点 \(1\)，\(1\leq n,m\leq1000\)；
测试点 \(2,3\)，没有 \(2\) 操作；
测试点 \(4,5\)，没有 \(3\) 操作；
测试点 \(6\)，树的生成方式是，对于 \(i(2\leq i \leq n)\)，在 \(1 \sim i-1\) 中随机选一个点作为 \(i\) 的父节点；
测试点 \(7\)，\(1\leq n,m\leq 5\times 10^4\)；
测试点 \(8\)，\(1\leq n \leq 5 \times 10^4\)；
测试点9,10，无特殊限制
对所有数据，\(1\leq n \leq 10^5\)，\(1\leq m \leq 10^5\)。
这题和 LCT 关系很大。
先说比较淳朴的树剖做法。先树剖，然后你考虑用 ODT 去维护每一段的信息。询问的时候也就是要求用线段树维护一个点的所有祖先中有多少个点他和他的父亲颜色不一样。询问2差分回答，询问3就是拍成 dfs 序后子树询问最大值。
现在只关注某一条重链。那么每次覆盖是一个前缀覆盖，那么颜色段数量每次最多增加一个，而覆盖的时候也是只会减不会增。所以对于一条重链他的均摊修改次数时 \(O(n)\) 的，对于所有重链来说颜色段均摊修改次数就是 \(O(nlogn)\) 的。那么就是说均摊有 \(O(nlog n)\) 次修改，使得一个点和他的父亲颜色不一样。如果我们可以知道用 ODT 找到每次改变的点这样的修改，然后用线段树暴力改，总复杂度 \(O(nlog^2n)\)
但是这个问题和 LCT 有什么关系呢？你会发现 操作 1 和 LCT 的 access 几乎一样。而 access 的复杂度证明就是和上面差不多，但是他用自平衡的 splay 替换了我们用的 set。如果你用 LCT 的话，这道题就是每次 access 后找到父亲和儿子不一样的地方，然后用线段树子树加。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,tp[N],fa[N],tr[N<<2],tg[N<<2],dep[N],in[N],sz[N],son[N],idx,ss[N],t[N],dfn[N];
set<pair<int,int> >s[N];
vector<int>g[N];
void pushdown(int o)
{
tr[o<<1]+=tg[o],tr[o<<1|1]+=tg[o];
tg[o<<1]+=tg[o],tg[o<<1|1]+=tg[o];
tg[o]=0;
}
void upd(int o,int l,int r,int x,int y,int z)
{
if(x<=l&&r<=y)
{
tg[o]+=z,tr[o]+=z;
return;
}
pushdown(o);
int md=l+r>>1;
if(md>=x)
upd(o<<1,l,md,x,y,z);
if(md<y)
upd(o<<1|1,md+1,r,x,y,z);
tr[o]=max(tr[o<<1],tr[o<<1|1]);
}
int ask(int o,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
return tr[o];
pushdown(o);
int md=l+r>>1,ret=0;
if(md>=x)
ret=ask(o<<1,l,md,x,y);
if(md<y)
ret=max(ret,ask(o<<1|1,md+1,r,x,y));
return ret;
}
void dfs(int x,int y)
{
fa[x]=y,sz[x]=1,dep[x]=dep[y]+1;
for(int v:g[x])
{
if(v^y)
{
dfs(v,x);
sz[x]+=sz[v];
if(sz[v]>sz[son[x]])
son[x]=v;
}
}
}
void sou(int x,int y,int d)
{
tp[x]=d;
in[x]=++idx,ss[idx]=sz[x];
dfn[idx]=x;
s[d].insert(make_pair(idx,idx));
if(son[x])
sou(son[x],x,d);
for(int v:g[x])
if(v^y&&v^son[x])
sou(v,x,v);
}
int lca(int x,int y)
{
while(tp[x]^tp[y])
{
if(dep[tp[x]]<dep[tp[y]])
swap(x,y);
x=fa[tp[x]];
}
if(in[x]<in[y])
return x;
return y;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<n;i++)
{
scanf("%d%d",&u,&v);
g[u].push_back(v),g[v].push_back(u);
}
dfs(1,0);
sou(1,0,1);
for(int i=1;i<=n;i++)
upd(1,1,n,in[i],in[i],dep[i]-1);
for(int i=1,op,x,y,z;i<=m;i++)
{
scanf("%d%d",&op,&x);
if(op==1)
{
int ls=0;
while(x)
{
auto itr=--s[tp[x]].upper_bound(make_pair(in[x],100000000));
for(auto it=s[tp[x]].begin();it!=itr;it++)
{
if(it!=s[tp[x]].begin())
upd(1,1,n,it->first,it->first+ss[it->first]-1,-1);
if(t[it->second])
upd(1,1,n,t[it->second],t[it->second]+ss[t[it->second]]-1,1),t[it->second]=0;
}
if(itr->second^in[x])
{
upd(1,1,n,in[x]+1,in[x]+ss[in[x]+1],1);
s[tp[x]].insert(make_pair(in[x]+1,itr->second));
}
else
{
if(ls!=t[in[x]]&&t[in[x]])
upd(1,1,n,t[in[x]],t[in[x]]+ss[t[in[x]]]-1,1);
}
if(itr!=s[tp[x]].begin())
upd(1,1,n,itr->first,itr->first+ss[itr->first]-1,-1);
s[tp[x]].erase(s[tp[x]].begin(),itr);
s[tp[x]].erase(itr);
s[tp[x]].insert(make_pair(in[tp[x]],in[x]));
if(t[in[x]]^ls&&ls)
upd(1,1,n,ls,ls+ss[ls]-1,-1);
t[in[x]]=ls;
ls=in[tp[x]];
x=fa[tp[x]];
}
}
else if(op==2)
{
scanf("%d",&y),z=lca(x,y);
printf("%d\n",1+ask(1,1,n,in[x],in[x])+ask(1,1,n,in[y],in[y])-2*ask(1,1,n,in[z],in[z]));
}
else
printf("%d\n",1+ask(1,1,n,in[x],in[x]+sz[x]-1));
}
}