【bzoj3091】 城市旅行

http://www.lydsy.com/JudgeOnline/problem.php?id=3091 (题目链接)

题意

　　给出一棵无根树，维护四个操作。link,cut,路径加法,路径期望查询。

Solution

　　右转题解→_→：PoPoQQQ

　　对于无法直接维护的值，我们可以考虑做差，或者是用别的比较好维护的值来加减乘除得到。

细节

　　全程LL，先翻转再打标记。

代码

// bzoj3091

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)

using namespace std;

const int maxn=50010;

int n,m,fa[maxn];

struct node {

	int son[2];

	LL sum,tag,rev,ans,val,lsum,rsum,size;

	int& operator [] (int x) {return son[x];}

}tr[maxn];

LL gcd(LL a,LL b) {return b==0 ? a : gcd(b,a%b);}

namespace LCT {

	void reverse(int k) {

		swap(tr[k][0],tr[k][1]);

		swap(tr[k].lsum,tr[k].rsum);

		tr[k].rev^=1;

	}

	void add(int k,LL val) {

		tr[k].val+=val;

		tr[k].sum+=tr[k].size*val;

		tr[k].tag+=val;

		tr[k].ans+=tr[k].size*(tr[k].size+1)*(tr[k].size+2)/6*val;

		tr[k].lsum+=tr[k].size*(tr[k].size+1)/2*val;

		tr[k].rsum+=tr[k].size*(tr[k].size+1)/2*val;

	}

	void pushdown(int k) {

		if (tr[fa[k]][0]==k || tr[fa[k]][1]==k) pushdown(fa[k]);

		int l=tr[k][0],r=tr[k][1];

		if (tr[k].rev) {

			if (l) reverse(l);

			if (r) reverse(r);

			tr[k].rev^=1;

		}

		if (tr[k].tag) {

			if (l) add(l,tr[k].tag);

			if (r) add(r,tr[k].tag);

			tr[k].tag=0;

		}

	}

	void pushup(int k) {

		int l=tr[k][0],r=tr[k][1];

		tr[k].size=tr[l].size+tr[r].size+1;

		tr[k].lsum=tr[l].lsum+(tr[l].size+1)*tr[k].val+tr[r].lsum+tr[r].sum*(tr[l].size+1);

		tr[k].rsum=tr[r].rsum+(tr[r].size+1)*tr[k].val+tr[l].rsum+tr[l].sum*(tr[r].size+1);

		tr[k].sum=tr[l].sum+tr[r].sum+tr[k].val;

		tr[k].ans=tr[l].ans+tr[r].ans+tr[l].lsum*(tr[r].size+1)+tr[r].rsum*(tr[l].size+1)+tr[k].val*(tr[l].size+1)*(tr[r].size+1);

	}

	void rotate(int x) {

		int y=fa[x],z=fa[y],l,r;

		l=tr[y][1]==x;r=l^1;

		if (tr[z][0]==y || tr[z][1]==y) tr[z][tr[z][1]==y]=x;

		fa[tr[x][r]]=y;fa[x]=z;fa[y]=x;

		tr[y][l]=tr[x][r];tr[x][r]=y;

		pushup(y);pushup(x);

	}

	void splay(int x) {

		pushdown(x);

		while (tr[fa[x]][0]==x || tr[fa[x]][1]==x) {

			int y=fa[x],z=fa[y];

			if (tr[z][0]==y || tr[z][1]==y) {

				if (tr[z][0]==y ^ tr[y][0]==x) rotate(x);

				else rotate(y);

			}

			rotate(x);

		}

	}

	void access(int x) {

		for (int y=0;x;y=x,x=fa[x]) splay(x),tr[x][1]=y,pushup(x);

	}

	void makeroot(int x) {

		access(x);splay(x);reverse(x);

	}

	void link(int x,int y) {

		makeroot(x);fa[x]=y;

	}

	void cut(int x,int y) {

		makeroot(x);access(y);splay(y);

		if (tr[y][0]==x && tr[x][1]==0)

			tr[y][0]=0,fa[x]=0,pushup(y);

	}

	void modify(int x,int y,LL val) {

		makeroot(x);access(y);splay(y);add(y,val);

	}

	int find(int x) {

		return fa[x] ? find(fa[x]) : x;

	}

	void query(int x,int y) {

		makeroot(x);access(y);splay(y);

		LL A=tr[y].ans,B=tr[y].size*(tr[y].size+1)/2;

		LL D=gcd(A,B);

		printf("%lld/%lld\n",A/D,B/D);

	}

}

using namespace LCT;

int main() {

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++) scanf("%lld",&tr[i].val);

	for (int u,v,i=1;i<n;i++) {

		scanf("%d%d",&u,&v);

		link(u,v);

	}

	for (int op,x,y,d,i=1;i<=m;i++) {

		scanf("%d%d%d",&op,&x,&y);

		if (op==1) if (find(x)==find(y)) cut(x,y);

		if (op==2) if (find(x)!=find(y)) link(x,y);

		if (op==3) {scanf("%d",&d);if (find(x)==find(y)) modify(x,y,d);}

		if (op==4) if (find(x)==find(y)) query(x,y);else puts("-1");

	}

	return 0;

}