2631: tree
Time Limit: 30 Sec Memory Limit: 128 MB
Submit: 1716 Solved: 576
[Submit][Status]
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
动态树编的还是不熟练，这道题的模数是刚刚爆int的(51061^2==2607225721>2147483647),如果用long long 又要TLE，所以必须用unsigned int.
这道题涉及到动态树的路径操作，具体用法是通过make_root()access()将一个路径上所有点集中到一个splay中。
还有一点，就是这类支持区间加，乘的题，标记应即为x*mul+plus，即先下放mul,在下放plus
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define MAXN 110000
#define MAXT MAXN*2
#define MAXV MAXN*2
#define MAXE MAXV*2
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define lch ch[now][0]
#define rch ch[now][1]
#define plus _plus
#define MOD 51061//刚刚爆int
typedef unsigned int qword;
inline int nextInt()
{
char ch;
int x=;
bool flag=false;
do
ch=(char)getchar(),flag=(ch=='-')?true:flag;
while(ch<''||ch>'');
do x=x*+ch-'';
while (ch=(char)getchar(),ch<='' && ch>='');
return x*(flag?-:);
} int n,m;
struct Edge
{
int np;
Edge *next;
}E[MAXE],*V[MAXV];
int tope=-;
int fa[MAXT];
int depth[MAXT];
inline void addedge(int x,int y)
{
E[++tope].np=y;
E[tope].next=V[x];
V[x]=&E[tope];
}
void dfs(int now)
{
Edge *ne;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==fa[now])continue;
fa[ne->np]=now;
depth[ne->np]=depth[now]+;
dfs(ne->np);
}
}
//------------------------Link Cut Tree------------------------
int pnt[MAXT],ch[MAXT][];
qword sum[MAXT],val[MAXT];
qword mult[MAXT],plus[MAXT];
bool flip[MAXT];
int stack[MAXT],tops=-;
int siz[MAXT];
void init()
{
int i;
for (i=;i<=n;i++)
{
pnt[i]=fa[i];
mult[i]=;
plus[i]=;
val[i]=sum[i]=;
flip[i]=false;
siz[i]=;
}
}
inline bool is_root(int now)//是splay上的根
{
return (!pnt[now]) || (ch[pnt[now]][]!=now && ch[pnt[now]][]!=now);
}
inline void up(int now)
{
sum[now]=(sum[lch]+sum[rch]+val[now])%MOD;
siz[now]=(siz[lch]+siz[rch]+)%MOD;
}
inline void reverse(int now)
{
if (!now)return;
swap(ch[now][],ch[now][]);
flip[now]^=;
}
inline void make_multiply(int now,qword v)//对于一个splay的子树加标记下放
{
mult[now]=mult[now]*v%MOD;
plus[now]=plus[now]*v%MOD;
sum[now]=sum[now]*v%MOD;
val[now]=val[now]*v%MOD;
}
inline void make_plus(int now,qword v)//同make_multiply
{
plus[now]=(plus[now]+v)%MOD;
sum[now]=(sum[now]+v*siz[now])%MOD;
val[now]=(val[now]+v)%MOD;
}
inline void down(int now)
{
if (flip[now])
{
reverse(ch[now][]);
reverse(ch[now][]);
flip[now]=false;
}
if (mult[now]!=)
{
make_multiply(ch[now][],mult[now]);
make_multiply(ch[now][],mult[now]);
mult[now]=;
}
if (plus[now])
{
make_plus(ch[now][],plus[now]);
make_plus(ch[now][],plus[now]);
plus[now]=;
}
}
inline void rotate(int now)
{
int p=pnt[now],anc=pnt[p];
if (is_root(now))throw ;
int dir=ch[p][]==now;
pnt[now]=anc;
if (!is_root(p))/**/
ch[anc][ch[anc][]==p]=now;
ch[p][-dir]=ch[now][dir];
pnt[ch[now][dir]]=p;
pnt[p]=now;
ch[now][dir]=p;
up(p);
up(now);
}
void splay(int now)
{
int x=now; while (!is_root(x))
{
stack[++tops]=x;
x=pnt[x];
}
stack[++tops]=x;
do{
down(stack[tops--]);
}while (tops>=);
if (is_root(now))return ;//先下放标记,否则access中自动接在其他点上面
while (!is_root(now))
{
int p=pnt[now],anc=pnt[p];
if (is_root(p))//注意判断的对象
{
rotate(now);
}else
{
if ((ch[anc][]==p) == (ch[p][]==now))
{
rotate(p);
rotate(now);
}else
{
rotate(now);
rotate(now);
}
}
}
}
void access(int now)//需要记忆！
{
int son=;
for (;now;now=pnt[son=now])
{
splay(now);
ch[now][]=son;
up(now);
}
// while (ch[now][0])
// now=ch[now][0];
// return now;
}
void make_root(int now)
{
access(now);
splay(now);
swap(ch[now][],ch[now][]);
reverse(ch[now][]);
reverse(ch[now][]);
//reverse(now);//注意
}
void cut(int x,int y)
{
make_root(x);
access(y);
splay(x);
ch[x][ch[x][]==y]=;
pnt[y]=;
up(x);
up(y);
}
void link(int x,int y)
{
// access(y);
splay(y);
make_root(x);
access(x);
splay(x);
pnt[x]=y;
up(y);
}
void scan(int now)
{
if (!now)return ;
down(now);
scan(lch);
printf("%d ",(int)val[now]);
scan(rch);
} int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int i;
int x,y,z;
int a,b,c,d;
scanf("%d%d",&n,&m);
for (i=;i<n;i++)
{
x=nextInt();y=nextInt();
//scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
scanf("\n");
dfs();
init();
char opt;
for (i=;i<m;i++)
{
opt=(int)getchar();
//scanf("%c",&opt);
if (opt=='+')
{
x=nextInt();y=nextInt();z=nextInt();
//scanf("%d%d%d\n",&x,&y,&z);
z%=MOD;
make_root(x);
access(y);
splay(y);
make_plus(y,z);
}else if (opt=='-')
{
a=nextInt();b=nextInt();c=nextInt();d=nextInt();
//scanf("%d%d%d%d\n",&a,&b,&c,&d);
cut(a,b);
link(c,d);
}else if (opt=='*')
{
x=nextInt();y=nextInt();z=nextInt();
//scanf("%d%d%d\n",&x,&y,&z);
z%=MOD;
make_root(x);
access(y);
splay(y);
make_multiply(y,z);
}else if (opt=='/')
{
x=nextInt();y=nextInt();
//scanf("%d%d\n",&x,&y);
make_root(x);
access(y);
splay(y);
printf("%d\n",(int)sum[y]);
}
}
return ;
}