# LCT萌新求助

@_tourist_  2020-08-04 10:42 回复
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200200;
const int MOD=51061;
int ADD(int x,int y){x+=y; return x>=MOD ? x-MOD : x;}
int MUL(int x,int y){return 1ll*x*y%MOD;}
int n,val[N],Q;

#define ls ch[x][0]
#define rs ch[x][1]
namespace LCT{
int getdir(int x){return (ch[fa[x]][1]==x);}//0:left 1:right
int isRoot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void pushup(int x){
sz[x]=sz[ls]+sz[rs]+1;
}
void pushdown(int x){
if(mul[x]!=1)
{
mul[x]=1;
}
{
}
if(rev[x])
{

if(ls) swap(ch[ls][0],ch[ls][1]), rev[ls]^=1;
if(rs) swap(ch[rs][0],ch[rs][1]), rev[rs]^=1;
rev[x]=0;
}
}
void pushall(int x){if(!isRoot(x)) pushall(fa[x]); pushdown(x);}
void rotate(int x){
int y=fa[x],z=fa[y],dirx=getdir(x),diry=getdir(y);
if(!isRoot(y)) ch[z][diry]=x;
ch[y][dirx]=ch[x][dirx^1]; if(ch[x][dirx^1]) fa[ch[x][dirx^1]]=y;
ch[x][dirx^1]=y; fa[y]=x; fa[x]=z;
pushup(y); pushup(x);
}
void splay(int x){
pushall(x);
int F=fa[x];
while(!isRoot(x))
{
if(!isRoot(F))
{
if(getdir(F)==getdir(x)) rotate(F);
else rotate(x);
}
rotate(x);
F=fa[x];
}
}
void access(int x){
for(int now=0;x!=0;now=x,x=fa[x])
{
splay(x);
ch[x][1]=now; pushup(x);
}
}
void makeroot(int x){
access(x);
splay(x);
rev[x]^=1; swap(ls,rs);
}
int findroot(int x){
access(x); splay(x);
while(ch[x][0])
{
pushdown(x);
x=ch[x][0];
}
splay(x);
return x;
}
makeroot(x);
fa[x]=y;
//pushup(y)？？？？
}
void cut(int x,int y){
makeroot(x);
access(y); splay(y);
fa[x]=0; ch[y][0]=0;
pushup(y);
}
void split(int x,int y){
makeroot(x);
access(y); splay(y);
}//y is the root

split(x,y);
}
void update_mul(int x,int y,int v){
split(x,y);
mul[y]=MUL(mul[y],v); sum[y]=MUL(sum[y],v);
}
int query(int x,int y){
split(x,y);
return sum[y];
}
}

int vis[N];
int main()
{
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&Q);
for(int i=1;i<n;i++)
{
int x,y; scanf("%d%d",&x,&y);
if(!vis[x]) LCT::init(x);
if(!vis[y]) LCT::init(y);
vis[x]=1; vis[y]=1;
}
while(Q--)
{
char opt[2]; scanf("%s",opt); getchar();
if(opt[0]=='+'){
int u,v,c; scanf("%d%d%d",&u,&v,&c);
} else if(opt[0]=='-'){
int u1,v1,u2,v2; scanf("%d%d%d%d",&u1,&v1,&u2,&v2);
LCT::cut(u1,v1);
} else if(opt[0]=='*'){
int u,v,c; scanf("%d%d%d",&u,&v,&c);
LCT::update_mul(u,v,c);
} else{
int u,v; scanf("%d%d",&u,&v);
printf("%d\n",LCT::query(u,v));
}
}
return 0;
}

@JK_LOVER 2020-08-04 10:46 回复 举报
void link(int x,int y){
makeroot(x);
fa[x]=y;
//pushup(y)？？？？
}

@JK_LOVER 2020-08-04 10:47 回复 举报

    void link(int x,int y){
makeroot(x);
access(y);
splay(y);
fa[x]=y;
pushup(y);
}