Lvat_s Blog

的确是好题。。。

根本不会，然后copy了PoPoQQQ大爷的代码

反正就是LCT乱搞

题解

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int Mod=10007,N=30005;

int n,m,vis[N],cnt,fa[N];

struct Line{
int k,b;
Line(){}
Line(int ks,int bs){k=ks;b=bs;}
friend Line operator+(Line A,Line B){return Line(A.k*B.k%Mod,(B.k*A.b+B.b)%Mod);}
int F(int x){return (k*x+b)%Mod;}
};

struct Node{
Line v,sum;
Node *ch[2],*fa,*spc;
Node(int k,int b);
void Pushup();
}*root[N],*Null;

Node::Node(int k,int b){ch[0]=ch[1]=fa=spc=Null;v=sum=Line(k,b);}
void Node::Pushup(){sum=ch[0]->sum+v+ch[1]->sum;}
bool Notroot(Node *x){return x->fa->ch[0]==x || x->fa->ch[1]==x;}
Node *GetNull(){Node *p=new Node(1,0);p->ch[0]=p->ch[1]=p->fa=p;return p;}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}}
Node *Findroot(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}
pair<int,int>exgcd(int a,int b){if(!b)return make_pair(1,0);pair<int,int>P=exgcd(b,a%b);return make_pair(P.second,P.first-a/b*P.second);}
int Inv(int x){int P=exgcd((x+Mod)%Mod,Mod).first;return (P%Mod+Mod)%Mod;}
void DFS(int u){vis[u]=cnt;if(vis[fa[u]]==cnt){root[u]->spc=root[fa[u]];return;}root[u]->fa=root[fa[u]];if(!vis[fa[u]])DFS(fa[u]);}

int Query(Node *x){
Node *rt=Findroot(x);
Access(rt->spc);
Splay(rt->spc);
int k=rt->spc->sum.k,b=rt->spc->sum.b;
if(k==1 && !(b==0 && x->sum.k==0))return b?-1:-2;
Access(x);
Splay(x);
return x->sum.F((Mod-b)*Inv(k-1)%Mod);
}

void Modify(Node *x,int k,Node *f,int b){
Node *rt=Findroot(x);
x->v.k=k;x->v.b=b;x->Pushup();
if(x==rt)x->spc=Null;
else {
	Access(x);
	Splay(x);
	x->ch[0]->fa=Null;
    x->ch[0]=Null;
    x->Pushup();
    if(Findroot(rt->spc)!=rt){
		Access(rt);
		Splay(rt);
		rt->fa=rt->spc;
		rt->spc=Null;
    }
}
Access(x);
Splay(x);
if(Findroot(f)==x){x->spc=f;}
else x->fa=f;
}

int main(){
freopen("2759.in","r",stdin);
freopen("2759.out","w",stdout);
scanf("%d",&n);
Null=GetNull();
for(int i=1;i<=n;i++){
	int k,f,b;
	scanf("%d %d %d",&k,&f,&b);
    fa[i]=f;
    root[i]=new Node(k,b);
}
for(int i=1;i<=n;i++){if(!vis[i]){cnt++;DFS(i);}}
scanf("%d",&m);
for(int i=1;i<=m;i++){
	char s[10];
	int x,k,p,b;
	scanf("%s",s);
	if(s[0]=='A'){scanf("%d",&x);printf("%d\n",Query(root[x]));}
	if(s[0]=='C'){scanf("%d %d %d %d",&x,&k,&p,&b);Modify(root[x],k,root[p],b);}
}
return 0;
}