bzoj2759

题解：

lct+解线性方程组

首先先把每一个环搞出来，然后再建立一个额外的点

然后解方程。。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N=,M=;

int n,Q,tim,fa[N],dir[N],x,k,p,b,vis[N],ch[N][],ni[N];

char s[];

int which(int x){return ch[fa[x]][]==x;}

struct node

{

    int k,b;

    node(){}

    node(int k,int b):k(k),b(b){}

    friend node operator + (const node &r1,const node &r2)

     {return node(r1.k*r2.k%M,(r2.k*r1.b%M+r2.b)%M);}

}a[N],sum[N];

void dfs(int x)

{

    if (vis[x])return;

    vis[x]=tim;

    if (vis[fa[x]]==tim)

     {

        dir[x]=fa[x];

        fa[x]=;

     }

    else dfs(fa[x]);

}

int isroot(int x){return !fa[x]||ch[fa[x]][which(x)]!=x;}

void pushup(int x)

{

    sum[x]=a[x];

    if (ch[x][])sum[x]=sum[ch[x][]]+a[x];

    if (ch[x][])sum[x]=sum[x]+sum[ch[x][]];

}

void rotate(int x)

{

    int y=fa[x],k=which(x);

    ch[y][k]=ch[x][k^];

    ch[x][k^]=y;

    if (!isroot(y))ch[fa[y]][which(y)]=x;

    fa[x]=fa[y];fa[y]=x;

    fa[ch[y][k]]=y;

    pushup(y);pushup(x);

}

void splay(int x)

{

    for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])

     if (!isroot(y))rotate((ch[y][]==x)==(ch[fa[y]][]==y)?y:x);

}

void access(int x)

{

    int t=;

    while(x)

     {

        splay(x);

        ch[x][]=t;

        pushup(x);

        t=x;x=fa[x];

     }

}

int findroot(int x)

{

    access(x);splay(x);

    while(ch[x][])x=ch[x][];

    splay(x);

    return x;

}

int inc(int x,int y)

{

    access(dir[y]);splay(dir[y]);

    splay(x);

    return x==dir[y]||!isroot(dir[y]);

}

void cut(int x){access(x);splay(x);ch[x][]=fa[ch[x][]]=;pushup(x);}

int main()

{

    ni[]=;

    for (int i=;i<M;i++)ni[i]=(M-M/i)*ni[M%i]%M;

    scanf("%d",&n);

    for (int i=;i<=n;i++)scanf("%d%d%d",&a[i].k,&fa[i],&a[i].b);

    for (int i=;i<=n;i++)

     if (!vis[i])tim++,dfs(i);

    scanf("%d",&Q);

    while (Q--)

     {

        scanf("%s",s+);

        if (s[]=='A')

         {

            scanf("%d",&x);

            access(x);splay(x);

            node t1=sum[x];

            int t=findroot(x);

            access(dir[t]);splay(dir[t]);

            node t2=sum[dir[t]];

            if (t2.k==)

             {

                if (t2.b)puts("-1");

                else puts("-2");

                continue;

             }

            int v1=ni[(-t2.k+M)%M]*t2.b%M;

            printf("%d\n",(t1.k*v1%M+t1.b)%M);

         }

        else

         {

            scanf("%d%d%d%d",&x,&k,&p,&b);

            access(x);splay(x);

            a[x]=node(k,b);pushup(x);

            int t=findroot(x);

            if (t==x)

             {

                if (findroot(p)==t)dir[t]=p;

                else dir[t]=,fa[t]=p;

             }

            else

             {

                if (inc(x,t))

                 {

                    cut(x);

                    access(t);splay(t);

                    fa[t]=dir[t];dir[t]=;

                    if (findroot(p)==x)dir[x]=p;

                    else fa[x]=p;

                 }

                else

                 {

                    cut(x);

                    if (findroot(p)==x)dir[x]=p;

                    else fa[x]=p;

                 }

             }

         }

     }

    return ;

}