题意
https://www.lydsy.com/JudgeOnline/problem.php?id=2759
思路
每个节点仅有一条有向出边， 这便是一棵基环内向树，我们可以把它在 \(\text{LCT}\) 内部当作有根树维护，外部再保存根的出边。
我们用一个结构体 \((K,B)\) 表示 \(y=Kx+B\) ，它的加法运算意义是将前者的 \(y\) 代入后者的 \(x\) 。一条路径 \((u,v)\) （ \(u\) 指向 \(v\) ）的 \(sum\) 就是在 \(v\) 的出边位置带入 \(x\) ，经过 \(sum\) 运算得到的 \(u\) 点的 \(y\) 值。
对于一个点 \(x\) ，可以先得到它的根 \(y\) 和它指向的点 \(z\) ，得出 \((z,y)\) 的 \(sum\) 函数为 \(f(x)=Kx+B\) ，设 \(z\) 节点的点权为 \(pw_z\)，则有如下关系：
\[\begin{align}\
f(pw_z)&=pw_z\notag\\
Kpw_z+B&=pw_z\notag\\
(1-K)pw_z&=B\notag\\
pw_z&={B\over 1-K}\notag
\end{align}
\]
f(pw_z)&=pw_z\notag\\
Kpw_z+B&=pw_z\notag\\
(1-K)pw_z&=B\notag\\
pw_z&={B\over 1-K}\notag
\end{align}
\]
不难得出，当 \(K=1\) 时，若 \(B=0\) ，则方程有多解，若 \(B\neq0\) ，则方程无解，否则就解出了 \(z\) 的值。
接下来只需询问路径 \((x,y)\) 的函数，然后求出 \(x\) 的权值即可。
代码
#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
const int N=3e4+5;
const int P=1e4+7;
int inv[P];
int ch[N][2],fa[N];
struct node
{
int K,B;
node(int _K=1,int _B=0){K=_K,B=_B;}
node operator +(const node &_)const
{
return node(K*_.K%P,(_.K*B+_.B)%P);
}
};
node nd[N],sum[N];
int Ifa[N];
int n,q;
void create(int x,node val)
{
ch[x][0]=ch[x][1]=fa[x]=0;
nd[x]=sum[x]=val;
}
bool isroot(int x){return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];}
void push_up(int x)
{
sum[x]=sum[ch[x][0]]+nd[x]+sum[ch[x][1]];
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=(x==ch[y][1]);
if(!isroot(y))ch[z][y==ch[z][1]]=x; fa[x]=z;
ch[y][k]=ch[x][!k]; if(ch[x][!k])fa[ch[x][!k]]=y;
ch[x][!k]=y,fa[y]=x;
push_up(y),push_up(x);
}
void splay(int x)
{
while(!isroot(x))
{
int y=fa[x],z=fa[y];
if(!isroot(y))(x==ch[y][1])==(y==ch[z][1])?rotate(y):rotate(x);
rotate(x);
}
}
void access(int x)
{
for(int y=0;x;y=x,x=fa[x])
splay(x),ch[x][1]=y,push_up(x);
}
int get_fa(int x)
{
access(x),splay(x);
if(!ch[x][0])return -1;
x=ch[x][0];
while(ch[x][1])x=ch[x][1];
splay(x);
return x;
}
int get_root(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(get_root(y)==x)return false;
fa[x]=y;
return true;
}
bool cut(int x)
{
access(x),splay(x);
if(!ch[x][0])return false;
fa[ch[x][0]]=0,ch[x][0]=0;
push_up(x);
return true;
}
void update(int x,node val)
{
nd[x]=sum[x]=val;
push_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=get_root(x);
if(!cut(x)){Ifa[x]=0;return;}
if(link(y,Ifa[y]))Ifa[y]=0;
}
int Solve(int x)
{
int y=get_root(x),z=Ifa[y];
node f=query(z);
if(f.K==1)return f.B==0?-2:-1;
int val=f.B*inv[(P+1-f.K)%P]%P;
f=query(x);
return (f.K*val+f.B)%P;
}
int main()
{
inv[0]=inv[1]=1;
FOR(i,2,P-1)inv[i]=(P-P/i)*inv[P%i]%P;
scanf("%d",&n);
FOR(i,0,n)create(i,node(1,0));
FOR(i,1,n)
{
int k,p,b;
scanf("%d%d%d",&k,&p,&b);
update(i,node(k,b));
Link(i,p);
}
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",Solve(a));
}
else if(op[0]=='C')
{
scanf("%d%d%d%d",&a,&k,&p,&b);
update(a,node(k,b));
Cut(a);
Link(a,p);
}
}
return 0;
}