P10660 BZOJ2759 一个动态树好题 题解

· · 题解

从题目名字看出此题需要用动态树解决。

对于任意 i，都有唯一的 p_i 与之对应，由 p_i 向 i 连边，n 种关系显然构成一基环树森林。对于环上的节点，一个点可以自己表示自己，所以可以直接解出该点的权值，其他点从环上的点直接推出即可。

考虑如何动态维护这个过程，一个点上对应的线性变换显然可以用矩阵刻画（其实只是不想动脑子），对于一棵基环树，我们把它多出来那一条边，和根节点的答案都存在根节点上（这样的话换根就要慎重一些了），询问时直接链乘积求出系数即可。

对于任意 \text{Link}(x,y) 操作，若 x,y 不连通则直接连边（注意此处 \text{MakeRoot}(x) 也没有影响，因为能连出边的点一定不属于一棵基环树）。否则算出 x 的答案，并把答案和这条边存在 x 上。

修改的时候，设此处原来的边为 (y,x)，现换为 (z,x)。那么我们先 \text{Cut}(x,y)（此处根节点需要特判，因为它连向父亲的边没有真实连上），然后 \text{Link}(x,z)，最后如果 x 不是根节点的话，要把 x 所属的基环树的那条虚边再 \text{Link} 一遍（因为修改后环可能被拆了，此时应该将它真实连上以保证正确性）。

最后关于无解和多解。可以证明，如果根无解，那么整棵树所有节点都无解，多解也有一样的性质。

#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
    char ch=getchar();
    T f=1;x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x*=f;rd(args...);
}
const int N=3e4+5,mod=10007;
struct Matrix{
    int m[2][2];
    Matrix(){memset(m,0,sizeof m);}
    Matrix(int _x){memset(m,0,sizeof m);m[0][0]=m[1][1]=_x;}
    Matrix friend operator+(Matrix a,Matrix b){
        Matrix c;
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)c.m[i][j]=(a.m[i][j]+b.m[i][j])%mod;
        return c;
    }
    Matrix friend operator*(Matrix a,Matrix b){
        Matrix c;
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                for(int k=0;k<=1;k++)(c.m[i][j]+=a.m[i][k]*b.m[k][j])%=mod;
        return c;
    }
};
inline int KSM(int x,int n){
    int ans=1;
    while(n){
        if(n&1)ans=ans*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return ans;
}
int n,q;
namespace LCT{
    int f[N],ch[N][2],tag[N];
    Matrix m[N],prd[N];
    struct{int x,y,ans;}nd[N];
    #define ls ch[p][0]
    #define rs ch[p][1]
    inline void PushUp(int p){prd[p]=prd[ls]*m[p]*prd[rs];}
    inline void Rev(int p){
        tag[p]^=1;swap(ls,rs);
        PushUp(p);
    }
    inline void PushDown(int p){
        if(!tag[p])return ;
        Rev(ls),Rev(rs);tag[p]=0;
    }
    inline int Get(int p){return ch[f[p]][1]==p;}
    inline int IsRoot(int p){return ch[f[p]][1]!=p&&ch[f[p]][0]!=p;}
    void Update(int p){
        if(!IsRoot(p))Update(f[p]);
        PushDown(p);
    }
    inline void Rotate(int x){
        int y=f[x],z=f[y],k=Get(x);
        if(!IsRoot(y))ch[z][Get(y)]=x;
        ch[y][k]=ch[x][!k],ch[x][!k]=y;
        f[y]=x,f[x]=z,f[ch[y][k]]=y;
        PushUp(y),PushUp(x);
    }
    inline void Splay(int x){
        Update(x);
        for(int fa=f[x];!IsRoot(x);Rotate(x),fa=f[x])
            if(!IsRoot(fa))Rotate(Get(fa)==Get(x)?fa:x);
    }
    inline int Access(int x){
        int p;
        for(p=0;x;p=x,x=f[x])
            Splay(x),ch[x][1]=p,PushUp(x);
        return p;
    }
    inline void MakeRoot(int x){
        x=Access(x);Rev(x);
    }
    inline int FindRoot(int p){
        p=Access(p);
        while(ls)p=ls,PushDown(p);
        return Splay(p),p;
    }
    inline void Link(int x,int y){
        if(FindRoot(x)==FindRoot(y)){
            MakeRoot(x);Access(y);
            Splay(x);Matrix mm=prd[ch[x][1]]*m[x];
            nd[x].x=x,nd[x].y=y;
            int k=(mm.m[0][0]+mod-1)%mod,b=mod-mm.m[1][0];
            if(k==0&&b==0)nd[x].ans=-2;
            else if(k==0)nd[x].ans=-1;
            else nd[x].ans=1ll*b*KSM(k,mod-2)%mod;
        }else{
            MakeRoot(x);
            Splay(x);f[x]=y;
        }
    }
    inline void Modify(int x,int k,int y,int b){
        int rt=FindRoot(x);
        Splay(x);
        m[x].m[0][0]=k,m[x].m[1][0]=b;
        PushUp(x);
        if(rt!=x){
            Access(x);Splay(x);
            f[ch[x][0]]=0,ch[x][0]=0;
            Link(x,y);
            Link(nd[rt].x,nd[rt].y);
        }
        else Link(x,y);
    }
    inline int Query(int p){
        int rt=FindRoot(p);Access(p);
        Splay(rt);
        int k=prd[ch[rt][1]].m[0][0],b=prd[ch[rt][1]].m[1][0];
        if(nd[rt].ans==-1)return -1;
        if(nd[rt].ans==-2)return -2;
        return (1ll*k*nd[rt].ans%mod+b)%mod;
    }
    #undef ls
    #undef rs 
}
int p[N];
using namespace LCT;
signed main(){
    rd(n);
    prd[0]=m[0]=Matrix(1);
    for(int i=1;i<=n;i++){
        int k,b;rd(k,p[i],b);
        m[i].m[0][0]=k;
        m[i].m[1][0]=b;
        m[i].m[1][1]=1;
    }
    for(int i=1;i<=n;i++)Link(i,p[i]);
    rd(q);
    while(q--){
        char s[3];int a,x,y,z;
        scanf("%s",s);
        if(s[0]=='A'){
            rd(a);
            printf("%d\n",Query(a));
        }else if(s[0]=='C'){
            rd(a,x,y,z);
            Modify(a,x,y,z);
        }
    }
    return 0;
}