bzoj 2631: tree — LCT
Contents
2631: tree
Time Limit: 30 Sec Memory Limit: 128 MB
Description
一棵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的余数。
Input
第一行两个整数n，q
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作
Output
对于每个/对应的答案输出一行
Sample Input
3 2
1 2
2 3
* 1 3 4
/ 1 1
1 2
2 3
* 1 3 4
/ 1 1
Sample Output
4
HINT
数据规模和约定
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
Source
LCT入门题，，
md一个%=写成了%改了我一天。。。
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define uint unsigned int
#define mod 51061
#define N 100010
inline int rd()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
int c[N][2],fa[N],sz[N];
uint lz1[N],lz2[N],v[N],sum[N];
bool rev[N];
int n,q;
#define ls c[x][0]
#define rs c[x][1]
bool isrt(int x){return x!=c[fa[x]][0]&&x!=c[fa[x]][1];}
inline void pd(int x)
{
uint mz;
if(rev[x])
{
rev[ls]^=1;rev[rs]^=1;
swap(ls,rs);rev[x]=0;
}
mz=lz2[x];lz2[x]=1;
if(mz!=1)
{
lz2[ls]=lz2[ls]*mz%mod;
lz2[rs]=lz2[rs]*mz%mod;
lz1[ls]=lz1[ls]*mz%mod;
lz1[rs]=lz1[rs]*mz%mod;
sum[ls]=sum[ls]*mz%mod;
sum[rs]=sum[rs]*mz%mod;
v[ls]=v[ls]*mz%mod;v[rs]=v[rs]*mz%mod;
}
mz=lz1[x];lz1[x]=0;
if(mz)
{
(lz1[ls]+=mz)%=mod;
(lz1[rs]+=mz)%=mod;
(sum[ls]+=sz[ls]*mz)%=mod;
(sum[rs]+=sz[rs]*mz)%=mod;
(v[ls]+=mz)%=mod;(v[rs]+=mz)%=mod;
}
}
inline void upd(int x)
{
sz[x]=sz[ls]+sz[rs]+1;
sum[x]=(v[x]+sum[ls]+sum[rs])%mod;
}
void rot(int x)
{
int y=fa[x],z=fa[y],l,r;
l=c[y][1]==x;r=l^1;
if(!isrt(y)) c[z][c[z][1]==y]=x;
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
upd(y);upd(x);
}
int st[N],tot;
void splay(int x)
{
tot=1;st[1]=x;
for(int i=x;!isrt(i);i=fa[i]) st[++tot]=fa[i];
for(int i=tot;i;i--) pd(st[i]);
int y,z;
while(!isrt(x))
{
y=fa[x];z=fa[y];
if(!isrt(y))
{
if((c[y][0]==x)^(c[z][0]==y)) rot(x);
else rot(y);
}
rot(x);
}
}
void acc(int x)
{
int t=0;
while(x)
{
splay(x);
rs=t;upd(x);
t=x;x=fa[x];
}
}
void rever(int x)
{
acc(x);
splay(x);
rev[x]^=1;
}
void mk(int x,int y)
{
rever(x);
acc(y);splay(y);
}
void link(int x,int y)
{
rever(x);
fa[x]=y;
}
void cut(int x,int y)
{
mk(x,y);
c[y][0]=fa[x]=0;
}
inline void mul(int x,int V)
{
(v[x]*=V)%=mod;
(sum[x]*=V)%=mod;
(lz2[x]*=V)%=mod;
(lz1[x]*=V)%=mod;
}
inline void add(int x,int V)
{
(v[x]+=V)%=mod;
(sum[x]+=V*sz[x])%=mod;
(lz1[x]+=V)%=mod;
}
int main()
{
n=rd();q=rd();
for(int i=1;i<=n;i++) lz2[i]=sz[i]=sum[i]=v[i]=1;
for(int i=1,x,y;i<n;i++)
{
x=rd();y=rd();
link(x,y);
}
char op[2];
int x,y,xx,yy,V;
while(q--)
{
scanf("%s",op);
if(op[0]=='*')
{
x=rd();y=rd();V=rd();
mk(x,y);mul(y,V);
}
else if(op[0]=='+')
{
x=rd();y=rd();V=rd();
mk(x,y);add(y,V);
}
else if(op[0]=='-')
{
x=rd();y=rd();xx=rd();yy=rd();
cut(x,y);link(xx,yy);
}
else
{
x=rd();y=rd();
mk(x,y);printf("%d\n",sum[y]);
}
}
return 0;
}
发表评论