[BZOJ 2759] 一个动态树好题

题目描述

首先这是个基环树。

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

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

还是有点难写的。

代码：

#include<bits/stdc++.h>

#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<mod;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

	n=Get();

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

		k[i]=Get(),p[i]=Get(),b[i]=Get();

		update(i);

	}

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

		if(Find_root(i)!=Find_root(p[i])) Link(i,p[i]);

	}

	for(int i=1;i<=n;i++) if(i==Find_root(i)) work(i);

	int m=Get();

	char op;

	int tim=0;

	while(m--) {

		while(op=getchar(),!isalpha(op));

		int a;

		if(op=='A') {

			a=Get();

			cout<<query(a)<<"\n";

		} else {

			a=Get();

			modify(a);

		}

	}

	return 0;

}