LCT的各种操作。。。
。
cut link add mul size rev query
写的效率不够高。。。
BZOJ上似乎TLE。
。。。
A1303. tree(伍一鸣)
时间限制：2.5s 内存限制：64.0MB
试题来源
2012中国国家集训队命题答辩
问题描写叙述
一棵n个点的树。每一个点的初始权值为1。
对于这棵树有q个操作，每一个操作为下面四种操作之中的一个：
+ u v c：将u到v的路径上的点的权值都加上自然数c。
- u1 v1 u2 v2：将树中原有的边(u1,v1)删除，增加一条新边(u2,v2)。保证操作完之后仍然是一棵树；
* u v c：将u到v的路径上的点的权值都乘上自然数c；
/ u v：询问u到v的路径上的点的权值和。求出答案对于51061的余数。
输入格式
第一行两个整数n，q
接下来n-1行每行两个正整数u。v，描写叙述这棵树
接下来q行，每行描写叙述一个操作
接下来n-1行每行两个正整数u。v，描写叙述这棵树
接下来q行，每行描写叙述一个操作
输出格式
对于每一个/相应的答案输出一行
例子输入
3 2
1 2
2 3
* 1 3 4
/ 1 1
1 2
2 3
* 1 3 4
/ 1 1
例子输出
4
数据规模和约定
10%的数据保证，1<=n，q<=2000
另外15%的数据保证。1<=n。q<=5*10^4，没有-操作，而且初始树为一条链
另外35%的数据保证，1<=n，q<=5*10^4。没有-操作
100%的数据保证，1<=n，q<=10^5，0<=c<=10^4
另外15%的数据保证。1<=n。q<=5*10^4，没有-操作，而且初始树为一条链
另外35%的数据保证，1<=n，q<=5*10^4。没有-操作
100%的数据保证，1<=n，q<=10^5，0<=c<=10^4
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int LL;
const int maxn=100100;
const LL mod=51061;
int ch[maxn][2],pre[maxn];
bool rev[maxn],rt[maxn];
LL size[maxn],key[maxn],add[maxn],mul[maxn],sum[maxn];
void update_add(int r,LL d)
{
if(!r) return ;
if(d==0) return ;
key[r]=(key[r]+d)%mod;
add[r]=(add[r]+d)%mod;
sum[r]=(size[r]*d+sum[r])%mod;
}
void update_mul(int r,LL d)
{
if(!r) return ;
if(d==1) return ;
sum[r]=(sum[r]*d)%mod;
key[r]=(key[r]*d)%mod;
mul[r]=(mul[r]*d)%mod;
add[r]=(add[r]*d)%mod;
}
void update_rev(int r)
{
if(!r) return ;
swap(ch[r][0],ch[r][1]);
rev[r]=rev[r]^1;
}
void push_down(int r)
{
if(!r) return ;
if(rev[r])
{
if(ch[r][0]) update_rev(ch[r][0]);
if(ch[r][1]) update_rev(ch[r][1]);
rev[r]=0;
}
if(mul[r]!=1)
{
if(ch[r][0]) update_mul(ch[r][0],mul[r]);
if(ch[r][1]) update_mul(ch[r][1],mul[r]);
mul[r]=1;
}
if(add[r])
{
if(ch[r][0]) update_add(ch[r][0],add[r]);
if(ch[r][1]) update_add(ch[r][1],add[r]);
add[r]=0;
}
}
void push_up(int r)
{
sum[r]=key[r]%mod;
size[r]=1;
if(ch[r][0])
{
sum[r]=(sum[r]+sum[ch[r][0]])%mod;
size[r]+=size[ch[r][0]];
}
if(ch[r][1])
{
sum[r]=(sum[r]+sum[ch[r][1]])%mod;
size[r]+=size[ch[r][1]];
}
}
void Rotate(int x)
{
int y=pre[x],kind=ch[y][1]==x;
ch[y][kind]=ch[x][!kind];
pre[ch[y][kind]]=y;
pre[x]=pre[y];
pre[y]=x;
ch[x][!kind]=y;
if(rt[y]) rt[y]=false,rt[x]=true;
else ch[pre[x]][ch[pre[x]][1]==y]=x;
push_up(y);
}
void P(int r)
{
if(!rt[r]) P(pre[r]);
push_down(r);
}
void Splay(int r)
{
P(r);
while(!rt[r])
{
int f=pre[r],ff=pre[f];
if(rt[f]) Rotate(r);
else if((ch[ff][1]==f)==(ch[f][1]==r)) Rotate(f),Rotate(r);
else Rotate(r),Rotate(r);
}
push_up(r);
}
int Access(int x)
{
int y=0;
for(;x;x=pre[y=x])
{
Splay(x);
rt[ch[x][1]]=true; rt[ch[x][1]=y]=false;
push_up(x);
}
return y;
}
void mroot(int r)
{
Access(r);
Splay(r);
update_rev(r);
}
void link(int u,int v)
{
mroot(u);
pre[u]=v;
}
void cut(int u,int v)
{
mroot(u);
Splay(v);
pre[ch[v][0]]=pre[v];
pre[v]=0;
rt[ch[v][0]]=true;
ch[v][0]=0;
push_up(v);
}
void Add(int u,int v,LL d)
{
mroot(u);
Access(v);
Splay(v);
update_add(v,d);
}
void Mul(int u,int v,LL d)
{
mroot(u);
Access(v);
Splay(v);
update_mul(v,d);
}
void debug();
void query(int u,int v)
{
mroot(u);
Access(v);
Splay(v);
//cout<<"size: "<<size[v]<<" sum: "<<sum[v]<<endl;
printf("%lld
",sum[v]);
}
struct Edge
{
int to,next;
}edge[maxn*2];
int Adj[maxn],Size;
void add_edge(int u,int v)
{
edge[Size].to=v; edge[Size].next=Adj[u]; Adj[u]=Size++;
}
int n,q;
void init()
{
Size=0;
for(int i=0;i<=n+10;i++)
{
Adj[i]=-1;
ch[i][0]=ch[i][1]=0;
pre[i]=0; rt[i]=true; rev[i]=false;
key[i]=1; size[i]=1; add[i]=0; mul[i]=1; sum[i]=1;
}
}
void dfs(int u)
{
for(int i=Adj[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(pre[v]!=0) continue;
pre[v]=u;
dfs(v);
}
}
void showit(int x)
{
if(x)
{
push_down(x);
showit(ch[x][0]);
printf("结点: %2d 左儿子: %2d 右儿子: %2d 父结点: %2d size: %2lld sum: %2lld key: %2lld
",
x,ch[x][0],ch[x][1],pre[x],size[x],sum[x],key[x]);
showit(ch[x][1]);
}
}
void debug()
{
for(int i=0;i<=n;i++)
{
if(rt[i])
{
cout<<"ROOT: "<<i<<endl;
showit(i);
cout<<"..........
";
}
}
}
int main()
{
while(scanf("%d%d",&n,&q)!=EOF)
{
init();
for(int i=0;i<n-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v); add_edge(v,u);
}
pre[1]=-1; dfs(1); pre[1]=0;
//debug();
char op[10];
while(q--)
{
scanf("%s",op);
if(op[0]=='+')
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
Add(u,v,c);
}
else if(op[0]=='-')
{
int u1,v1,u2,v2;
scanf("%d%d%d%d",&u1,&v1,&u2,&v2);
cut(u1,v1);
link(u2,v2);
}
else if(op[0]=='*')
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
Mul(u,v,c);
}
else if(op[0]=='/')
{
int u,v;
scanf("%d%d",&u,&v);
query(u,v);
}
//debug();
}
}
return 0;
}