有一棵树，初始每个节点有不同的颜色

操作1：根节点到x的路径上的点 染上一种没有出现过的颜色

操作2：操作1后把x换成根

操作3：定义点x的点权为x到根节点路径上不同颜色的数量，查询x的子树点权和

 

LCT+线段树+dfs序

dfs一遍得到每个点的dfs序，

以及每个点子树的dfs序范围,记点x的子树dfs序范围为 [Lx,Rx]

线段树以dfs序为顺序维护

 

操作1就是access，

一条Preferred Path 上所有点的颜色相同

在轻重链交换的时候才会涉及到点权的修改

如果lct上父节点x和子节点y之间的边由重链变轻链，那么lct上 以子节点y为根的子树的所有点 的点权减1

实现就是找到t的Auxiliary Tree 上深度最小的点z， 区间[Lz,Rz] 减1

如果lct上父节点x和子节点y之间的边由轻链变重链，那么lct上 以子节点y为根的子树的所有点 的点权加1

实现就是找到t的Auxiliary Tree 上深度最小的点z， 区间[Lz,Rz] 加1

 

操作2就是LCT的换根操作

不用刻意的去维护换根对线段树的影响，因为换根之前会执行操作1，access

点到新的根节点路径上的颜色数量 就等于 点到原来根节点路径上的颜色数量

 

查询操作：

分析点x和根节点root 子树的包含关系

若x==root，那就是查询整棵树

若x在root的子树内，直接查x的子树

若root在x的子树内，设root在x的子节点p的子树内，那就是查询整棵树除去p的子树的部分

查询子树就是 线段树按dfs序维护的一段连续的区间

 

#include
     
      #include
      
       #include
       
        #define N 100001using namespace std;typedef long long LL;int n;int front[N],to[N<<1],nxt[N<<1],tot;int id[N],dy[N],lst[N],tim;int dep[N];int lim,F[N][18];int fa[N],ch[N][2],root;bool rev[N];LL sum[N<<2];int siz[N<<2],tag[N<<2];int st[N],top;void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void add(int u,int v){    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;}void dfs(int x){    id[x]=++tim;    dy[tim]=x;    for(int i=front[x];i;i=nxt[i])        if(to[i]!=fa[x])        {            dep[to[i]]=dep[x]+1;            F[to[i]][0]=x;            fa[to[i]]=x;            dfs(to[i]);        }    lst[x]=tim;}void build(int k,int l,int r){    siz[k]=r-l+1;    if(l==r)    {        sum[k]=dep[dy[l]];        return;    }    int mid=l+r>>1;    build(k<<1,l,mid);    build(k<<1|1,mid+1,r);    sum[k]=sum[k<<1]+sum[k<<1|1];}void tagging(int k,int w){    sum[k]+=w*siz[k];    tag[k]+=w;}void push_down(int k){    tagging(k<<1,tag[k]);    tagging(k<<1|1,tag[k]);    tag[k]=0;}void change(int k,int l,int r,int opl,int opr,int w){    if(l>=opl && r<=opr)    {        tagging(k,w);        return;    }    if(tag[k]) push_down(k);    int mid=l+r>>1;    if(opl<=mid) change(k<<1,l,mid,opl,opr,w);    if(opr>mid) change(k<<1|1,mid+1,r,opl,opr,w);    sum[k]=sum[k<<1]+sum[k<<1|1];}void Change(int x,int w){    if(x==root) change(1,1,n,1,n,w);    else if(id[root]>id[x] && id[root]<=lst[x])        {        int t=root,c=dep[root]-dep[x]-1;        for(int i=lim;i>=0;--i)            if(c&(1<
        
         1) change(1,1,n,1,id[t]-1,w);        if(lst[t]
         
          >1; LL res=0;    if(opl<=mid) res+=query(k<<1,l,mid,opl,min(mid,opr));    if(opr>mid) res+=query(k<<1|1,mid+1,r,max(mid+1,opl),opr);    return res;}double Query(int x){    if(x==root) return 1.0*query(1,1,n,1,n)/n;    else if(id[root]>id[x] && id[root]<=lst[x])    {        int t=root,c=dep[root]-dep[x]-1;        for(int i=lim;i>=0;--i)            if(c&(1<
          
           1) res+=query(1,1,n,1,id[t]-1); if(lst[t]