[BZOJ 2759] 一个动态树好题

首先这是个基环树。

然后根节点一定会连出去一条非树边。通过一个环就可以解除根的答案，然后其他节点的答案就可以由根解出来。

因为要修改\(p_i\)，所以我们用\(lct\)。

还是有点难写的。

代码：

#include
    
     #define ll long long#define N 30005#define ls ch[v][0]#define rs ch[v][1]using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=10007;ll inv[mod];int n;int k[N],b[N];int p[N];int fa[N],ch[N][2];int rev[N];int A[N],B[N];int val[N];void update(int v) {    A[v]=(A[ls]*k[v])%mod;    B[v]=(B[ls]*k[v]+b[v])%mod;    A[v]=(A[v]*A[rs])%mod;    B[v]=(B[v]*A[rs]+B[rs])%mod;}bool isroot(int v) {return v!=ch[fa[v]][0]&&v!=ch[fa[v]][1];}void rot(int v) {    int f=fa[v],gr=fa[f];    int sn=v==ch[f][1],son=ch[v][!sn];    if(!isroot(f)) ch[gr][f==ch[gr][1]]=v;    ch[f][sn]=son,ch[v][!sn]=f;    fa[v]=gr,fa[f]=v;    if(son) fa[son]=f;    update(f),update(v);}void splay(int v) {    while(!isroot(v)) {        int f=fa[v],gr=fa[f];        if(!isroot(f)) rot(f==ch[gr][1]^v==ch[f][1]?f:v);        rot(v);    }}void access(int v) {    int tem=0;    while(v) {        splay(v);        rs=tem;        update(v);        tem=v,v=fa[v];    }}int Find_root(int v) {    access(v);    splay(v);    while(ls) v=ls;    return v;}void Link(int v,int f) {    splay(v);    fa[v]=f;}void Cut(int v) {    access(v),splay(v);    fa[ls]=0;    ls=0;    update(v);}void dfs(int v) {    if(!v) return ;    dfs(ls),dfs(rs);}void work(int v) {    access(p[v]);    splay(p[v]);    int na=A[p[v]]%mod;    int nb=B[p[v]]%mod;    na=(1-na+mod)%mod;    if(!na) {        if(!nb) val[v]=-2;        else val[v]=-1;    } else val[v]=inv[na]*nb%mod;}int query(int v) {    int rt=Find_root(v);    access(v),splay(v);    if(val[rt]<0) return val[rt];    else return (val[rt]*A[v]+B[v])%mod;}void modify(int v) {    int top=Find_root(v);    Cut(v);    k[v]=Get(),p[v]=Get(),b[v]=Get();    update(v);    if(Find_root(v)!=Find_root(p[v])) Link(v,p[v]);    if(Find_root(top)!=Find_root(p[top])) Link(top,p[top]);    work(Find_root(v)),work(Find_root(top));}int main() {    A[0]=1;    inv[0]=inv[1]=1;    for(int i=2;i