题意

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\)，则有如下关系：

不难得出，当 \(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;

}