Tsinsen A1303. tree(伍一鳴) LCT
來源：程序員人生 發布時間：2014-11-19 08:32:49 閱讀次數：3336次
LCT的各種操作。。。。
cut link add mul size rev query
寫的效力不夠高。。。BZOJ上似乎TLE。。。。
A1303. tree(伍1鳴)
時間限制：2.5s 內存限制：64.0MB
總提交次數：727 AC次數：238
平均分：45.59
將本題分享到：
查看未格式化的試題 提交 試題討論
問題描寫
1棵n個點的樹，每一個點的初始權值為1。對這棵樹有q個操作，每一個操作為以下4種操作之1：
+ u v c：將u到v的路徑上的點的權值都加上自然數c；
- u1 v1 u2 v2：將樹中原本的邊(u1,v1)刪除，加入1條新邊(u2,v2)，保證操作完以后依然是1棵樹；
* u v c：將u到v的路徑上的點的權值都乘上自然數c；
/ u v：詢問u到v的路徑上的點的權值和，求出答案對51061的余數。
輸入格式
第1行兩個整數n，q
接下來n⑴行每行兩個正整數u，v，描寫這棵樹
接下來q行，每行描寫1個操作
輸出格式
對每一個/對應的答案輸出1行
樣例輸入
3 2
1 2
2 3
* 1 3 4
/ 1 1
樣例輸出
4
數據范圍和約定
10%的數據保證，1<=n，q<=2000
另外15%的數據保證，1<=n，q<=5*10^4，沒有-操作，并且初始樹為1條鏈
另外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]=⑴;
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⑴;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v); add_edge(v,u);
}
pre[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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
