题解：P10661 BZOJ3779 重组病毒

· · 题解

Solution

LCT 复习就写两题吧，感觉 NOI 不会考。

由于染色操作十分特殊，不难发现：同一类型的病毒，在所有时刻都是连续的。那么一个点所花费的时间，就是它到根路径上颜色连续段的个数。

对于一条边，如果它相连的两个点颜色不同，权值为 1，否则为 0。则颜色连续段个数就是该节点到根路径权值和加 1。

而染色就非常像 \rm Access 操作。因此你可以快速维护权值变化。

唉但是你发现统计答案比较困难 /ll

假设当前的根是 r，我们查询了 u。

此时 u 的子树和以 1 为根的子树是一样的。

如图。黑色子树内的每条边，它的贡献都是边权 \times 儿子节点的子树大小，而红色树链上的每条边的贡献是边权 \times 黑色子树大小。

求出 LCA 后，可以用树状数组等数据结构维护。

我们将所有边分为三类：紫色表示 u 到 1 的路径上的点，红色表示包含 r 的一个 u 儿子的子树内的边，黑色表示其他边。

黑色的边对答案的贡献仍然为边权 \times 儿子节点的子树大小，紫色边对答案的贡献变为边权 \times (n- 儿子节点的子树大小 )，红色边只有在 u 到 r 的路径上才会有贡献。

这还是可以用树状数组维护。

捋一捋树状数组维护什么（首先要拍成 DFS 序）

  1. 每个点到 1 的权值和与边权 \times 儿子子树大小之和。这样每个边进行修改的时候顺带区间修改即可。

注意整棵树最开始我们认为所有边的边权都是 1。可以通过自底向上不断 \rm Access 得到。

  1. 子树内边权 \times 儿子子树大小之和。这个可以随手单点修改。

复杂度 O(n \log n)，完全没必要树链剖分，但是可能要开 3 个树状数组。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,m,rt=1,tp[MAXN],fa[MAXN][20],dep[MAXN],tot,dfn[MAXN],sze[MAXN];
vector<int> G[MAXN];
struct Node {
    int s[2],fa,flp,l,r;
}t[MAXN];
void flip(int u) {
    return swap(t[u].s[0],t[u].s[1]),t[u].flp^=1,swap(t[u].l,t[u].r),void();
}
void push_down(int u) {
    if(t[u].flp) flip(t[u].s[0]),flip(t[u].s[1]);
    return t[u].flp=0,void();   
}
void push_up(int u) {
    if(t[u].s[0]) t[u].l=t[t[u].s[0]].l; else t[u].l=u;
    if(t[u].s[1]) t[u].r=t[t[u].s[1]].r; else t[u].r=u;
    return ;    
}
int is_root(int u) {
    return u!=t[t[u].fa].s[0]&&u!=t[t[u].fa].s[1];  
}
int get(int u) {
    return u==t[t[u].fa].s[1];  
}
void rotate(int u) {
    int fa=t[u].fa,s=get(u),op=get(fa);
    if(!is_root(fa)) t[t[fa].fa].s[op]=u;t[u].fa=t[fa].fa;
    t[fa].s[s]=t[u].s[s^1],t[t[u].s[s^1]].fa=fa;
    t[u].s[s^1]=fa,t[fa].fa=u;
    return push_up(fa),push_up(u),void();   
}
void PUSH_DOWN(int u) {
    if(!is_root(u)) PUSH_DOWN(t[u].fa);
    return push_down(u),void(); 
}
void splay(int u) {
    PUSH_DOWN(u);
    for(int f;f=t[u].fa,!is_root(u);rotate(u)) if(!is_root(f)) rotate(get(u)==get(f)?f:u);
    return ;
}
pair<int,vector<pair<int,int>>> access(int u) {
    int lst=0; vector<pair<int,int>> ans;
    while(u) {
        splay(u);
        if(lst) ans.push_back({t[lst].l,u});
        if(t[u].s[1]) ans.push_back({u,t[t[u].s[1]].l});
        t[u].s[1]=lst,push_up(u),lst=u,u=t[u].fa;
    }
    return {lst,ans};
}
void dfs(int u,int f) {
    t[u].fa=f,dep[u]=dep[f]+1,dfn[u]=++tot,sze[u]=1,fa[u][0]=f;
    ffor(i,1,19) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(auto v:G[u]) if(v!=f) dfs(v,u),sze[u]+=sze[v];
    return ;
}
int jump(int u,int dt) {
    ffor(i,0,19) if(dt&(1<<i)) u=fa[u][i];
    return u;
}
int lca(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);
    u=jump(u,dep[u]-dep[v]);
    if(u==v) return u;
    roff(i,19,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
struct BIT {
    vector<int> vc;
    void build(int n) {return vc.resize(n+10),void();}
    void update(int pos,int v) {
        while(pos<=n) vc[pos]+=v,pos+=pos&-pos;
        return ;
    }
    int query(int pos) {
        int ans=0;
        while(pos) ans+=vc[pos],pos-=pos&-pos;
        return ans; 
    }
    int query(int l,int r) {
        return query(r)-query(l-1); 
    }
}s1,s2,s3;
void change(int i) {
    if(!tp[i]) {
        tp[i]=1;
        s1.update(dfn[i],1),s1.update(dfn[i]+sze[i],-1);
        s2.update(dfn[i],sze[i]),s2.update(dfn[i]+sze[i],-sze[i]);
        s3.update(dfn[i],sze[i]);
    }
    else {
        tp[i]=0;
        s1.update(dfn[i],-1),s1.update(dfn[i]+sze[i],1);
        s2.update(dfn[i],-sze[i]),s2.update(dfn[i]+sze[i],sze[i]);
        s3.update(dfn[i],-sze[i]);  
    }
    return ;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    ffor(i,1,n) t[i].l=t[i].r=i;
    ffor(i,1,n-1) {
        int u,v;
        cin>>u>>v,G[u].push_back(v),G[v].push_back(u);  
    }
    dfs(1,0),s1.build(n),s2.build(n),s3.build(n);
    ffor(i,2,n) {
        tp[i]=1;
        s1.update(dfn[i],1),s1.update(dfn[i]+sze[i],-1);
        s2.update(dfn[i],sze[i]),s2.update(dfn[i]+sze[i],-sze[i]);
        s3.update(dfn[i],sze[i]);
    }
    ffor(i,1,m) {
        string S;
        int x;
        cin>>S>>x;
        if(S=="RELEASE") {
            auto vc=access(x).second;
            for(auto pr:vc) {
                int u=pr.first,v=pr.second;
                if(fa[u][0]==v) change(u);
                else change(v);
            }
        }
        else if(S=="RECENTER") {
            auto pr=access(x);
            auto vc=pr.second;
            auto id=pr.first;
            flip(id);
            for(auto pr:vc) {
                int u=pr.first,v=pr.second;
                if(fa[u][0]==v) change(u);
                else change(v);
            }
            rt=x;
        }
        else {
            int ans=0,u=x,r=rt,l=lca(u,r);
            if(l!=u) {
                int cnt_ot=s1.query(dfn[u])+s1.query(dfn[r])-2*s1.query(dfn[l]);
                ans=s3.query(dfn[u]+1,dfn[u]+sze[u]-1)+sze[x]*cnt_ot;
                cout<<fixed<<setprecision(10)<<1.0*ans/sze[u]+1<<'\n';
            }
            else if(r!=u) {
                int kel=jump(r,dep[r]-dep[u]-1);
                int purple=n*s1.query(dfn[u])-2*s2.query(dfn[u]),black=s3.query(n)-s3.query(dfn[kel],dfn[kel]+sze[kel]-1);
                cout<<fixed<<setprecision(10)<<1.0*(purple+black)/(n-sze[jump(r,dep[r]-dep[u]-1)])+1+s1.query(dfn[r])-s1.query(dfn[u])<<'\n';
            }
            else {
                int purple=n*s1.query(dfn[u])-2*s2.query(dfn[u]),black=s3.query(n);
                cout<<fixed<<setprecision(10)<<1.0*(purple+black)/n+1<<'\n';    
            }
        }
    }
    return 0;
}