[BZOJ3091] 城市旅行
Description
.jpg)
Input
.jpg)
Output
.jpg)
Sample Input
4 5
1 3 2 5
1 2
1 3
2 4
4 2 4
1 2 4
2 3 4
3 1 4 1
4 1 4
Sample Output
16/3
6/1
HINT
对于所有数据满足 (1leq Nleq 50,000 1leq Mleq 50,000 1leq Aileq 10^6 1leq Dleq 100 1leq U,Vleq N)
试题分析
LCT一眼。
然后关键是维护信息：(sz,sl,sr,sum,st,val)分别表示Splay大小，权值与左边长度乘积的前缀和，权值与右边长度乘积的前缀和，子树和，答案，根节点权值。
那么更新如下：
inline void update(int x){
sz[x]=sz[lc]+sz[rc]+1;
sum[x]=sum[lc]+sum[rc]+val[x];
sl[x]=sl[lc]+sl[rc]+(sz[lc]+1)*(val[x]+sum[rc]); //左边的前缀和+右边的前缀和+左边让右边向右移的那些位乘上右边的子树和，这里是展开形式
sr[x]=sr[rc]+sr[lc]+(sz[rc]+1)*(val[x]+sum[lc]);//同上
st[x]=st[lc]+st[rc]+(sz[lc]+1)*sl[rc]+(sz[rc]+1)*sr[lc]+val[x]*(sz[lc]+1)*(sz[rc]+1);//根节点的权值，两边信息与两边在根节点处合并
}
注意常数和细节就没了。。。 为什么数据那么水，暴力水了rk1
- 注意一下交换左右儿子的时候sl和sr也要交换
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
inline int read(){
int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int INF = 2147483600;
const int MAXN = 50010;
int N,M; LL val[MAXN+1];
int ch[MAXN+1][2],fa[MAXN+1];
int dep[MAXN+1]; bool col[MAXN+1];
LL tag_val[MAXN+1];
LL sz[MAXN+1]; LL sum[MAXN+1];
LL sl[MAXN+1],sr[MAXN+1],st[MAXN+1];
inline void Union(int son,int f,int x){ch[f][x]=son; fa[son]=f;}
inline int chd(int x){return ch[fa[x]][0]==x?0:1;}
inline bool nroot(int x){return (ch[fa[x]][0]==x)|(ch[fa[x]][1]==x);}
inline void Colorf(int x){swap(ch[x][0],ch[x][1]); swap(sl[x],sr[x]); col[x]^=1; return ;}
inline void Add_val(int x,LL a){
val[x]+=a; tag_val[x]+=a;
sum[x]+=sz[x]*a; sl[x]+=sz[x]*(sz[x]+1)/2*a;
sr[x]+=sz[x]*(sz[x]+1)/2*a; st[x]+=(sz[x]+2)*(sz[x]+1)*sz[x]/6*a;
return ;
}
inline void pushdown(int x){
if(col[x]){Colorf(ch[x][0]); Colorf(ch[x][1]); col[x]=0;}
if(tag_val[x]){Add_val(ch[x][0],tag_val[x]); Add_val(ch[x][1],tag_val[x]); tag_val[x]=0;}
}
inline void update(int x){
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
sl[x]=sl[ch[x][0]]+(sz[ch[x][0]]+1)*(sum[ch[x][1]]+val[x])+sl[ch[x][1]];
sr[x]=sr[ch[x][1]]+(sz[ch[x][1]]+1)*(sum[ch[x][0]]+val[x])+sr[ch[x][0]];
st[x]=st[ch[x][0]]+st[ch[x][1]]+sl[ch[x][0]]*(sz[ch[x][1]]+1)+sr[ch[x][1]]*(sz[ch[x][0]]+1)+val[x]*(sz[ch[x][0]]+1)*(sz[ch[x][1]]+1);
return ;
}
inline void rotate(int x){
int y=fa[x],z=fa[y];
int k=ch[y][1]==x,w=ch[x][k^1];
if(nroot(y)) ch[z][ch[z][1]==y]=x;
ch[y][k]=w;ch[x][k^1]=y;
fa[x]=z;fa[y]=x; if(w) fa[w]=y; update(y); update(x);
}
inline void pushup(int x){
if(nroot(x)) pushup(fa[x]);
pushdown(x);
}
inline void Splay(int x){
int y=x; pushup(x);
while(nroot(x)){
y=fa[x]; if(nroot(y)) rotate((chd(x)==0)^(chd(y)==0)?x:y);
rotate(x);
} return ;
}
inline void access(int x){
for(int y=0;x;y=x,x=fa[x]) {
Splay(x); ch[x][1]=y; update(x);
} return ;
}
inline void chroot(int x){access(x); Splay(x); Colorf(x);}
inline int findroot(int x){ while(fa[x]) x=fa[x]; return x;}
inline void split(int x,int y){chroot(x); access(y); Splay(y); return ;}
inline void link(int x,int y){
if(findroot(x)!=findroot(y)) chroot(x),fa[x]=y;
}
inline void cut(int x,int y){
split(x,y); if(fa[x]==y){
fa[x]=ch[y][0]=0; update(y);
}return ;
}
inline void Add(int x,int y,LL d){
split(x,y); Add_val(y,d); return ;
}
inline LL gcd(LL a,LL b){
if(!b) return a;
return gcd(b,a%b);
}
int main(){
N=read(),M=read();
for(int i=1;i<=N;i++) val[i]=read(),update(i);
for(int i=2;i<=N;i++){
int u=read(),v=read();
link(u,v);
} for(int i=1;i<=M;i++){
int opr=read();
if(opr==1){
int u=read(),v=read(); cut(u,v);
} else if(opr==2){
int u=read(),v=read(); link(u,v);
} else if(opr==3){
int u=read(),v=read(),d=read();
if(findroot(u)==findroot(v)) Add(u,v,d);
} else if(opr==4){
int x=read(),y=read();
if(findroot(x)==findroot(y)){
split(x,y); LL z=st[y],d=(sz[y]*(sz[y]+1))>>1;
LL dt=gcd(z,d); printf("%lld/%lld
",z/dt,d/dt);
} else puts("-1");
}
}
return 0;
}