BZOJ3091: 城市旅行

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#define MAXN 50010
using namespace std;
map<int,int> Edge[MAXN];
int n,m;
int top=0,stack[MAXN];
struct Link_Cut_Tree{
	int f,size,flag,son[2];
	long long val,sum,lsum,rsum,exp,c;//exp==expectation
}a[MAXN];
inline int read(){
	int date=0,w=1;char c=0;
	while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
	while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
	return date*w;
}
long long gcd(long long x,long long y){
	if(!y)return x;
	return gcd(y,x%y);
}
inline bool isroot(int rt){
	return a[a[rt].f].son[0]!=rt&&a[a[rt].f].son[1]!=rt;
}
inline void pushup(int rt){
	if(!rt)return;
	int lson=a[rt].son[0],rson=a[rt].son[1];
	a[rt].sum=a[lson].sum+a[rson].sum+a[rt].val;
	a[rt].size=a[lson].size+a[rson].size+1;
	a[rt].lsum=a[lson].lsum+a[rson].lsum+(a[rt].val+a[rson].sum)*(a[lson].size+1);
	a[rt].rsum=a[rson].rsum+a[lson].rsum+(a[lson].sum+a[rt].val)*(a[rson].size+1);
	a[rt].exp=a[lson].exp+a[rson].exp+a[rt].val*(a[lson].size+1)*(a[rson].size+1)+a[lson].lsum*(a[rson].size+1)+a[rson].rsum*(a[lson].size+1);
}
inline void reverse(int rt){
	if(!rt)return;
	a[rt].flag^=1;
	swap(a[rt].son[0],a[rt].son[1]);
	swap(a[rt].lsum,a[rt].rsum);
}
inline void change(int rt,long long c){
	if(!rt)return;
	long long x=1LL*a[rt].size*(a[rt].size+1)/2,y=1LL*a[rt].size*(a[rt].size+1)*(a[rt].size+2)/6;
	a[rt].val+=c;
	a[rt].c+=c;
	a[rt].sum+=c*a[rt].size;
	a[rt].lsum+=x*c;
	a[rt].rsum+=x*c;
	a[rt].exp+=c*y;
}
inline void pushdown(int rt){
	if(!rt)return;
	if(a[rt].flag){
		reverse(a[rt].son[0]);
		reverse(a[rt].son[1]);
		a[rt].flag=0;
	}
	if(a[rt].c){
		change(a[rt].son[0],a[rt].c);
		change(a[rt].son[1],a[rt].c);
		a[rt].c=0;
	}
}
inline void turn(int rt){
	int x=a[rt].f,y=a[x].f,k=a[x].son[0]==rt?1:0;
	if(!isroot(x)){
		if(a[y].son[0]==x)a[y].son[0]=rt;
		else a[y].son[1]=rt;
	}
	a[rt].f=y;a[x].f=rt;a[a[rt].son[k]].f=x;
	a[x].son[k^1]=a[rt].son[k];a[rt].son[k]=x;
	pushup(x);pushup(rt);
}
void splay(int rt){
	top=0;
	stack[++top]=rt;
	for(int i=rt;!isroot(i);i=a[i].f)stack[++top]=a[i].f;
	while(top)pushdown(stack[top--]);
	while(!isroot(rt)){
		int x=a[rt].f,y=a[x].f;
		if(!isroot(x)){
			if((a[y].son[0]==x)^(a[x].son[0]==rt))turn(rt);
			else turn(x);
		}
		turn(rt);
	}
}
void access(int rt){
	for(int i=0;rt;i=rt,rt=a[rt].f){
		splay(rt);
		a[rt].son[1]=i;
		pushup(rt);
	}
}
inline void makeroot(int rt){access(rt);splay(rt);reverse(rt);}
int findroot(int rt){
	access(rt);splay(rt);
	while(a[rt].son[0])rt=a[rt].son[0];
	return rt;
}
inline void split(int x,int y){makeroot(x);access(y);splay(y);}
inline void link(int x,int y){makeroot(x);a[x].f=y;}
inline void cut(int x,int y){
	split(x,y);
	if(a[y].son[0]==x&&a[x].f==y&&!a[x].son[1])a[x].f=a[y].son[0]=0;
	pushup(y);
}
inline void update(int x,int y,int k){
	split(x,y);
	change(y,k);
}
inline void query(int x,int y){
	long long on,down,t;
	split(x,y);
	on=a[y].exp;
	down=1LL*a[y].size*(a[y].size+1)/2;
	t=gcd(on,down);
	printf("%lld/%lld\n",on/t,down/t);
}
void work(){
	int f,x,y,k;
	while(m--){
		f=read();x=read();y=read();
		switch(f){
			case 1:{
				if(Edge[x][y]){
					cut(x,y);
					Edge[x][y]=Edge[y][x]=0;
				}
				break;
			}
			case 2:{
				if(findroot(x)!=findroot(y)){
					link(x,y);
					Edge[x][y]=Edge[y][x]=1;
				}
				break;
			}
			case 3:{
				k=read();
				if(findroot(x)!=findroot(y))break;
				update(x,y,k);
				break;
			}
			case 4:{
				if(findroot(x)!=findroot(y))printf("-1\n");
				else query(x,y);
				break;
			}
		}
	}
}
void init(){
	int x,y;
	n=read();m=read();
	for(int i=1;i<=n;i++){
		a[i].val=read();
		pushup(i);
	}
	for(int i=1;i<n;i++){
		x=read();y=read();
		Edge[x][y]=Edge[y][x]=1;
		link(x,y);
	}
}
int main(){
	init();
	work();
    return 0;
}