BZOJ 4817: [Sdoi2017]树点涂色（LCT+树剖+线段树）

题目描述

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

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

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

• 1 x

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

• 2 x y

求 xx 到 yy 的路径的权值。

• 3 x

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

Bob一共会进行 mm 次操作

输入输出格式

输入格式：

第一行两个数 n,mn,m 。

接下来 n-1n−1 行，每行两个数 a,ba,b ，表示 aa 与 bb 之间有一条边。

接下来 mm 行，表示操作，格式见题目描述

输出格式：

每当出现2,3操作，输出一行。

如果是2操作，输出一个数表示路径的权值

如果是3操作，输出一个数表示权值的最大值

输入输出样例

输入样例#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\leq10001≤n,m≤1000

测试点2、3，没有2操作

测试点4、5，没有3操作

测试点6，树的生成方式是，对于 i(2\leq i \leq n)i(2≤i≤n) ，在1到 i-1i−1 中随机选一个点作为i的父节点。

测试点7， 1\leq n,m\leq 500001≤n,m≤50000

测试点8， 1\leq n \leq 500001≤n≤50000

测试点9,10，无特殊限制

对所有数据， 1\leq n \leq 10^51≤n≤105 ， 1\leq m \leq 10^51≤m≤105

时间限制：1s

空间限制：128MB

题解

照例先膜一发大佬

说真的是道好题，LCT，树剖，dfs序，线段树都得用上

然后抄题解抄得不亦乐乎悲催的没有发现一个地方我和大佬思路是完全不一样的……

后来因为这个地方调了整整一个小时……我少了一个小时的睡觉时间！！！

先讲个思路……

操作一

因为颜色都不一样，也没有必要维护颜色了

然后我们能发现，任何时候同一个颜色必定是一条链，而且深度严格递增

很显然，因为每一次颜色修改只会在到根的路径上进行

所以每一个颜色都可以用LCT中的splay来维护了

并且我们发现，操作一不就是LCT中的access么？

操作二

每一个颜色都在一个splay中

所以一条路径上的颜色数量就是跨过了几个splay，也就是经过了几条虚边

于是split就好了显然是行不通的，因为因为乱搞会破坏掉关系

然后可以考虑用树上差分

$f[x]+f[y]-2*f[lca(x,y)]+1$就是这条路径上的颜色数量了（lca被减了两次要加回来）（f表示到根节点的虚边数量）

然后考虑怎么维护$f$

刚开始时是节点的深度

然后显然access的时候会对$f$有影响，一条边变虚，一条边变实

所以只要把原来的虚边指向的子树答案全部+1，实边指向的子树答案全部-1

这就是一个子树操作啦

用线段树+dfs序，可以很轻松的完成子树操作

操作三

查询其实和修改差不多

直接线段树查询即可

ps：写的树剖求LCA，结果因为原树和splay都要维护father，看了看大佬的板子只用了一个数组，结果莫名其妙T到死……算了滚去睡觉了(¦3[▓▓]实在太困了……

//minamoto
#include<iostream>
#include<cstdio>
using std::swap;
using std::max;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
char obuf[1<<24],*o=obuf;
inline void print(int x){
    if(x>9) print(x/10);
    *o++=x%10+48;
}
const int N=100005,M=N*20;
int fa[N],f[N],ch[N][2],sz[N],son[N],dfn[N],rk[N];
int dep[N],top[N],L[M],R[M],mx[M],lz[M],rs[N],mid[M];
int head[N],Next[N<<1],ver[N<<1];
int n,m,cnt,num,tot;
inline void add(int u,int v){
    ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
    ver[++tot]=u,Next[tot]=head[v],head[v]=tot;
}
void dfs1(int u){
    sz[u]=1,dep[u]=dep[f[u]]+1;
    dfn[u]=++num,rk[num]=u;
    for(int i=head[u];i;i=Next[i]){
        int v=ver[i];
        if(v==f[u]) continue;
        fa[v]=f[v]=u;
        dfs1(v);
        sz[u]+=sz[v];
        if(!son[u]||sz[v]>sz[son[u]]) son[u]=v;
    }
    rs[u]=num;
}
void dfs2(int u){
    if(!top[u]) top[u]=u;
    if(!son[u]) return;
    top[son[u]]=top[u],dfs2(son[u]);
    for(int i=head[u];i;i=Next[i]){
        int v=ver[i];
        if(v!=f[u]&&v!=son[u]) dfs2(v);
    }
}
inline int LCA(int u,int v){
    while(top[u]!=top[v])
    dep[top[u]]>dep[top[v]]?u=f[top[u]]:v=f[top[v]];
    return dep[u]<dep[v]?u:v;
}
inline void build(int p,int l,int r){
    L[p]=l,R[p]=r,mid[p]=(l+r)>>1;
    if(l==r)return (void)(mx[p]=dep[rk[l]]);
    build(p<<1,l,mid[p]),build(p<<1|1,mid[p]+1,r);
    mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
#define pushdown if(lz[p]) update(p<<1,L[p],mid[p],lz[p]),update(p<<1|1,mid[p]+1,R[p],lz[p]),lz[p]=0
void update(int p,int l,int r,int v){
    if(L[p]==l&&R[p]==r){mx[p]+=v,lz[p]+=v;return;}
    pushdown;
    if(r<=mid[p]) update(p<<1,l,r,v);
    else if(l>mid[p]) update(p<<1|1,l,r,v);
    else update(p<<1,l,mid[p],v),update(p<<1|1,mid[p]+1,r,v);
    mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
int get(int v){
    int p=1;
    while(L[p]!=R[p]){
        pushdown;p=(p<<1)+(v>mid[p]);
        /*pushdown后面逗号竟然死循环了……*/
    }
    return mx[p];
}
int ask(int p,int l,int r){
    if(L[p]==l&&R[p]==r) return mx[p];
    pushdown;
    if(r<=mid[p]) return ask(p<<1,l,r);
    if(l>mid[p]) return ask(p<<1|1,l,r);
    return max(ask(p<<1,l,mid[p]),ask(p<<1|1,mid[p]+1,r));
}
#undef pushdown
bool isroot(int x){
    return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
void rotate(int x){
    int y=fa[x],z=fa[y],d=ch[y][1]==x;
    if(!isroot(y)) ch[z][ch[z][1]==y]=x;
    fa[x]=z,fa[y]=x,fa[ch[x][d^1]]=y,ch[y][d]=ch[x][d^1],ch[x][d^1]=y;
}
void splay(int x){
    for(int y=fa[x];!isroot(x);y=fa[x]){
        if(!isroot(y))
        rotate(x);
        rotate(x);
    }
}
int findroot(int x){
    while(ch[x][0]) x=ch[x][0];
    return x;
}
void access(int x){
    for(int w,y=0;x;x=fa[y=x]){
        splay(x);
        if(ch[x][1]) w=findroot(ch[x][1]),update(1,dfn[w],rs[w],1);
        if((ch[x][1]=y)) w=findroot(y),update(1,dfn[w],rs[w],-1);
        /*把原来的子树变为虚的，整个子树的答案+1
        然后新的子树答案-1*/
    }
}
int main(){
    //freopen("testdata.in","r",stdin);
    int n=read(),m=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        add(u,v);
    }
    dfs1(1),dfs2(1),build(1,1,n);
    while(m--){
        int opt=read(),x=read();
        switch(opt){
            case 1:{
                access(x);
                break;
            }
            case 2:{
                int y=read();
                print(get(dfn[x])+get(dfn[y])-get(dfn[LCA(x,y)])*2+1),*o++='\n';
                break;
            }
            case 3:{
                print(ask(1,dfn[x],rs[x])),*o++='\n';
                break;
            }
        }
    }
    fwrite(obuf,o-obuf,1,stdout);
    return 0;
}