bzoj4817 [Sdoi2017]树点涂色

Description

Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：

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

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

3 x y:在以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

正解：$link-cut tree$+树链剖分+线段树。

这道题很巧妙啊。。利用$LCT$的神奇性质完美地解决了询问$1$的棘手操作。

首先我们注意到，询问$1$其实就是$LCT$中的$access$操作。我们可以直接维护每个点到根节点的权值，然后利用$access$操作来处理这个问题。

我们在$access$操作的时候，直接将当前点原来的实儿子所在的子树权值$+1$，当前待接上的实儿子所在子树权值$-1$，就能完美地处理这个操作了。注意，这里指的实儿子一定是在原树中深度最浅的点。我比较偷懒，就直接暴力找$splay$中深度最小的点。具体解释的话，画个图就能理解了，看下代码应该能弄懂吧。。

对于询问$2$，我们可以发现，路径上的权值就是$val[x]+val[y]-2*val[lca(x,y)]+1$。这个式子是很好画图证明的。

首先，$lca$的两个儿子颜色是不可能相同的，所以我们分两种情况讨论一下，一种是$lca$和其中一个儿子颜色相同，一种是$lca$和两个儿子颜色都不同。这样我们就能很容易地得出上述结论。

对于询问$3$，我们直接区间查询，询问子树中的权值最大值就行了。

以上操作，维护权值都是用线段树，求$lca$写树链剖分比较方便。然后我们就能$AC$此题了，虽然复杂度还是很玄学。。

第一次$bzoj \ rank1$。。

 //It is made by wfj_2048~

 #include <algorithm>

 #include <iostream>

 #include <complex>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #define inf (1<<30)

 #define N (100010)

 #define ls (x<<1)

 #define rs (x<<1|1)

 #define il inline

 #define RG register

 #define ll long long

 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

 using namespace std;

 struct edge{ int nt,to; }g[*N];

 int head[N],n,m,num;

 struct tree_cut{

     int top[N],fa[N],son[N],sz[N],dep[N],pos[N],tid[N],ed[N],cnt;

     il void dfs1(RG int x,RG int p){

     fa[x]=p,dep[x]=dep[p]+,sz[x]=; RG int v;

     for (RG int i=head[x];i;i=g[i].nt){

         v=g[i].to; if (v==p) continue;

         dfs1(v,x),sz[x]+=sz[v];

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

     }

     return;

     }

     il void dfs2(RG int x,RG int p,RG int anc){

     top[x]=anc,tid[x]=++cnt,pos[cnt]=x;

     if (son[x]) dfs2(son[x],x,anc); RG int v;

     for (RG int i=head[x];i;i=g[i].nt){

         v=g[i].to; if (v==p || v==son[x]) continue;

         dfs2(v,x,v);

     }

     ed[x]=cnt; return;

     }

     il int lca(RG int u,RG int v){

     while (top[u]!=top[v]){

         if (dep[top[u]]<dep[top[v]]) swap(u,v);

         u=fa[top[u]];

     }

     return dep[u]<dep[v] ? u : v;

     }

 }tree;

 struct segment_tree{

     int mx[*N],lazy[*N];

     il void pushdown(RG int x){

     mx[ls]+=lazy[x],mx[rs]+=lazy[x];

     lazy[ls]+=lazy[x],lazy[rs]+=lazy[x];

     lazy[x]=; return;

     }

     il void build(RG int x,RG int l,RG int r){

     if (l==r){ mx[x]=tree.dep[tree.pos[l]]; return; }

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

     build(ls,l,mid),build(rs,mid+,r);

     mx[x]=max(mx[ls],mx[rs]); return;

     }

     il void update(RG int x,RG int l,RG int r,RG int xl,RG int xr,RG int v){

     if (xl<=l && r<=xr){ mx[x]+=v,lazy[x]+=v; return; }

     if (lazy[x]) pushdown(x); RG int mid=(l+r)>>;

     if (xr<=mid) update(ls,l,mid,xl,xr,v);

     else if (xl>mid) update(rs,mid+,r,xl,xr,v);

     else update(ls,l,mid,xl,mid,v),update(rs,mid+,r,mid+,xr,v);

     mx[x]=max(mx[ls],mx[rs]); return;

     }

     il int querymax(RG int x,RG int l,RG int r,RG int xl,RG int xr){

     if (xl<=l && r<=xr) return mx[x];

     if (lazy[x]) pushdown(x); RG int mid=(l+r)>>;

     if (xr<=mid) return querymax(ls,l,mid,xl,xr);

     else if (xl>mid) return querymax(rs,mid+,r,xl,xr);

     else return max(querymax(ls,l,mid,xl,mid),querymax(rs,mid+,r,mid+,xr));

     }

     il int ask(RG int x){ return querymax(,,n,tree.tid[x],tree.tid[x]); }

 }seg;

 struct link_cut_tree{

     int ch[N][],fa[N];

     il int isroot(RG int x){

     return ch[fa[x]][]!=x && ch[fa[x]][]!=x;

     }

     il void rotate(RG int x){

     RG int y=fa[x],z=fa[y],k=ch[y][]==x;

     if (!isroot(y)) ch[z][ch[z][]==y]=x;

     fa[x]=z,ch[y][k^]=ch[x][k],fa[ch[x][k]]=y;

     ch[x][k]=y,fa[y]=x; return;

     }

     il void splay(RG int x){

     while (!isroot(x)){

         RG int y=fa[x],z=fa[y];

         if (!isroot(y)){

         if ((ch[y][]==x)^(ch[z][]==y)) rotate(x);

         else rotate(y);

         }

         rotate(x);

     }

     return;

     }

     il void access(RG int x){

     RG int t=;

     while (x){

         splay(x);

         if (ch[x][]){

         RG int y=ch[x][]; while (ch[y][]) y=ch[y][];

         seg.update(,,n,tree.tid[y],tree.ed[y],);

         }

         if (t){

         RG int y=t; while (ch[y][]) y=ch[y][];

         seg.update(,,n,tree.tid[y],tree.ed[y],-);

         }

         ch[x][]=t,t=x,x=fa[x];

     }

     return;

     }

 }lct;

 il void insert(RG int from,RG int to){

     g[++num]=(edge){head[from],to},head[from]=num; return;

 }

 il int gi(){

     RG int x=,q=; RG char ch=getchar();

     while ((ch<'' || ch>'') && ch!='-') ch=getchar();

     if (ch=='-') q=-,ch=getchar();

     while (ch>='' && ch<='') x=x*+ch-,ch=getchar();

     return q*x;

 }

 il void work(){

     n=gi(),m=gi();

     for (RG int i=,u,v;i<n;++i) u=gi(),v=gi(),insert(u,v),insert(v,u);

     tree.dfs1(,),tree.dfs2(,,),seg.build(,,n);

     for (RG int i=;i<=n;++i) lct.fa[i]=tree.fa[i];

     for (RG int i=,type,x,y;i<=m;++i){

     type=gi(); if (type==) x=gi(),lct.access(x);

     if (type==){

         x=gi(),y=gi(); RG int Lca=tree.lca(x,y);

         printf("%d\n",seg.ask(x)+seg.ask(y)-*seg.ask(Lca)+);

     }

     if (type==) x=gi(),printf("%d\n",seg.querymax(,,n,tree.tid[x],tree.ed[x]));

     }

     return;

 }

 int main(){

     File("paint");

     work();

     return ;

 }

巴特西