BZOJ2759 一个动态树好题

题目

有\(N\)个未知数\(x[1..n]\)和\(N\)个等式组成的同余方程组：
\(x[i]=k[i]*x[p[i]]+b[i] mod 10007\)
其中，\(k[i],b[i],x[i]∈[0,10007)∩Z\)
你要应付\(Q\)个事务，每个是两种情况之一：
一.询问当前\(x[a]\)的解
\(A\ a\)
无解输出-1
\(x[a]\)有多解输出-2
否则输出\(x[a]\)
二.修改一个等式
\(C\ a\ k[a]\ p[a]\ b[a]\)

思路¹

此题一直有点迷，在paulliant大佬的指点下，勉强口胡一份题解。

首先不难发现，这是一个树形结构，每个点仅有一条有向出边，知道了每个点的父亲就能知道这个点，所以这是一棵基环树，然后我们用一个结构体表示当前点与它父亲的依赖关系。\((K,B)\)表示\(x=fa[x]*K+B\)

由于是单向边的有根树，所以每条边都指向它的父亲。所以对于LCT中的一条路径\((u,v)\)来说，\(sum[rt]=(node){K,B}\)表示\(u=Kv+B\)，合并什么的还是很好推的。

还有一题小R与手机和此题有几分相像。

struct node{
    int k,b;
    node operator + (const node& res)const{
        return (node){k*res.k%P,(res.k*b%P+res.b)%P};
    }
}

然后如果存在了环的话，可以先把它存下来，等之后有点被删掉了之后在加上去。之后询问的时候由于形成了环，所以就可以得到解的情况了。

代码

#include<bits/stdc++.h>
#define M 100005
using namespace std;
const int P=1e4+7;
int inv[M],Ifa[M];
int n;
struct node{
    int k,b;
    node operator + (const node& res)const{
        return (node){k*res.k%P,(res.k*b%P+res.b)%P};
    }
}val[M],sum[M];
struct LCT{
    int ch[M][2],fa[M];
    void up(int p){
        sum[p]=sum[ch[p][0]]+val[p]+sum[ch[p][1]];
    }
    void create(int x,node d){
        ch[x][0]=ch[x][1]=fa[x]=0;
        val[x]=sum[x]=d;
    }
    bool isrt(int x){
        return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],k=ch[y][1]==x;
        if(!isrt(y))ch[z][ch[z][1]==y]=x;fa[x]=z;
        ch[y][k]=ch[x][!k];fa[ch[x][!k]]=y;
        ch[x][!k]=y;fa[y]=x;
        up(y);up(x);
    }
    void splay(int x){
        while(!isrt(x)){
            int y=fa[x],z=fa[y];
            if(!isrt(y))
                (ch[y][1]==x^ch[z][1]==y)?rotate(x):rotate(y);
            rotate(x);
        }
    }
    void access(int x){
        for(int y=0;x;y=x,x=fa[x])
            splay(x),ch[x][1]=y,up(x);
    }
    int findrt(int x){
        access(x);splay(x);
        while(ch[x][0])x=ch[x][0];
        splay(x);return x;
    }
    bool link(int x,int y){
        splay(x);
        if(findrt(y)==x)return 0;
        fa[x]=y;
        return 1;
    }
    bool cut(int x){
        access(x),splay(x);
        if(!ch[x][0])return 0;
        fa[ch[x][0]]=0;ch[x][0]=0;
        up(x);
        return 1;
    }
    void update(int x,node d){
        val[x]=sum[x]=d;
        up(x);
        splay(x);
    }
    node query(int x){
        access(x),splay(x);
        return sum[x];
    }
    void Link(int x,int y){
        if(!link(x,y))Ifa[x]=y;
    }
    void Cut(int x){
        int y=findrt(x);
        if(!cut(x)){Ifa[x]=0;return;}
        if(link(y,Ifa[y]))Ifa[y]=0;
    }
    int solve(int x){
        int y=findrt(x),z=Ifa[y];
        node f=query(z);
        if(f.k==1)return f.b==0?-2:-1;
        int vl=f.b*inv[(P+1-f.k)%P]%P;
        f=query(x);
        return (f.k*vl+f.b)%P;
    }
}Tr;
int main(){
    inv[0]=inv[1]=1;
    for(int i=2;i<=P-1;i++)inv[i]=(P-P/i)*inv[P%i]%P;
    scanf("%d",&n);
    for(int i=0;i<=n;i++)Tr.create(i,(node){1,0});
    for(int i=1;i<=n;i++){
        int k,p,b;
        scanf("%d%d%d",&k,&p,&b);
        Tr.update(i,(node){k,b});
        Tr.Link(i,p);
    }
    int q;
    scanf("%d",&q);
    while(q--){
        char op[5];int a,k,p,b;
        scanf("%s",op);
        if(op[0]=='A'){
            scanf("%d",&a);
            printf("%d\n",Tr.solve(a));
        }
        else {
            scanf("%d%d%d%d",&a,&k,&p,&b);
            Tr.update(a,(node){k,b});
            Tr.Cut(a);
            Tr.Link(a,p);
        }
    }
    return 0;
}

[BZOJ 2759 一个动态树好题（动态树）]↩

</section>

BZOJ2759 一个动态树好题

题目

思路1

代码

思路¹