2016-06-01 08:50:36
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2631
注意加和乘的标记下传问题。
还有就是split后，要分清x和y哪个是祖先。
pushup在access和rotate后都要进行。
这题还卡常数，开ll就会T，开unsigned int即可。
#include<bits/stdc++.h>
#define inf 1000000000
#define uint unsigned int
#define N 100005
#define mod 51061
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,q;
char ch[];
namespace LCT{
int ch[N][],fa[N],sz[N];bool rev[N];
uint cj[N],add[N],val[N],sum[N];
inline bool isroot(int x){
if(ch[fa[x]][]!=x&&ch[fa[x]][]!=x)return ;return ;
}
void change(int x,int c,int a){
if(!x)return;
val[x]=(val[x]*c+a)%mod;
sum[x]=(sum[x]*c+a*sz[x])%mod;
add[x]=(add[x]*c+a)%mod;
cj[x]=(cj[x]*c)%mod;
}
void pushdown(int x){
if(rev[x]){
rev[ch[x][]]^=;rev[ch[x][]]^=;rev[x]^=;
swap(ch[x][],ch[x][]);
}
if(cj[x]!=||add[x]!=){
change(ch[x][],cj[x],add[x]);
change(ch[x][],cj[x],add[x]);
}
cj[x]=;add[x]=;
}
void Pushdown(int x){
if(!isroot(x))Pushdown(fa[x]);
pushdown(x);
}
void pushup(int x){
sum[x]=(sum[ch[x][]]+sum[ch[x][]]+val[x])%mod;
sz[x]=(sz[ch[x][]]+sz[ch[x][]]+)%mod;
}
void rotate(int x){
int y=fa[x],k=ch[y][]==x;
if(!isroot(y))ch[fa[y]][ch[fa[y]][]==y]=x;
fa[x]=fa[y];
fa[ch[x][!k]]=y;
fa[y]=x;
ch[y][k]=ch[x][!k];
ch[x][!k]=y;
pushup(y);pushup(x);
}
void splay(int x){
Pushdown(x);
for(int y=fa[x];!isroot(x);y=fa[x]){
if(!isroot(y)){
if((ch[fa[y]][ch[fa[y]][]==y])!=(ch[y][]==x))rotate(x);
else rotate(y);
}rotate(x);
}
}
inline void access(int x){
int y=;
while(x){
splay(x);
ch[x][]=y;pushup(x);
x=fa[y=x];
}
}
inline void moveroot(int x){
access(x);splay(x);rev[x]^=;
}
inline void link(int x,int y){
moveroot(x);fa[x]=y;splay(x);
}
inline void cut(int x,int y){
moveroot(x);access(y);splay(y);ch[y][]=fa[x]=;
}
inline void split(int x,int y){
moveroot(y);access(x);splay(x);
}
}
int main(){
n=read();q=read();
for(int i=;i<=n;i++)LCT::val[i]=LCT::sum[i]=LCT::cj[i]=LCT::sz[i]=;
for(int i=;i<n;i++)LCT::link(read(),read());
while(q--){
scanf("%s",ch);
int u=read(),v=read();
if(ch[]=='+')LCT::split(u,v),LCT::change(u,,read());
else if(ch[]=='-'){
LCT::cut(u,v);u=read();v=read();LCT::link(u,v);
}
else if(ch[]=='*')LCT::split(u,v),LCT::change(u,read(),);
else LCT::split(u,v),printf("%d\n",LCT::sum[u]%mod);
}
return ;
}
2631: tree
Time Limit: 30 Sec Memory Limit: 128 MB
Submit: 3385 Solved: 1137
[Submit][Status][Discuss]
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