[bzoj 3091] 城市旅行

维护一片点带权的森林. 森林最初是一棵N个点的树, 接着有M个操作: 删边, 连边, 路径加, 询问某路径上任取两点 (可相同) 路径上权值之和的期望 (输出一个既约分数). (1≤N≤5*10^4, 1≤M≤5*10^4, 前三种操作不合法则忽略, 询问的两点不连通则输出-1) 前三种是LCT的经典操作, 第四种是在问什么呢?

根据题意, 任取两点的含义是, 所有子路径被选中的概率相等. 路径上共有n个点, 则子路径有条. 要算期望, 只需要知道子路径权和之和.

记子路径权和之和为, 子树大小为n尝试建立递推关系. 平衡树上, 以当前点为界, 序列被分为三段. 不含当前点的子路径的贡献是, 含当前点的子路径有条, 当前点的贡献是. 发现左子树的每一个后缀都有种组合方式形成一条包含当前点的路径, 即左子树的每一个后缀都贡献次. 右子树同理. 记前缀和的和为, 后缀和的和为, 那么, 完整的递推式为:

怎样在下传标记的时候维护这些量呢? 设加上, 则和都加上. 位置的点被包含在条子路径中, 于是应加上, 拆开, 应用一, 二阶幂和的公式即得.

虽然严格来说这道题可能爆unsigned long long, 但是实际数据比较良心.

typedef unsigned long long ull;
const int N = 5e4;

struct Node {
	Node* ch[2], * fa;
	ull ss, pre, suf, sum, v;
	int n, d, t;
	bool rev;

	Node();
	void add(int);

	void reverse()
	{
		rev = !rev;
		swap(ch[0], ch[1]);
		ch[0]->t = 0;
		ch[1]->t = 1;
		swap(suf, pre);
	}

	void up()
	{
		Node* &lc = ch[0], * &rc = ch[1];
		pre = lc->pre + rc->pre + (lc->sum + v)*(rc->n + 1);
		suf = rc->suf + lc->suf + (rc->sum + v)*(lc->n + 1);
		ss = lc->ss + rc->ss + v*(lc->n + 1)*(rc->n + 1)
			+ lc->suf*(rc->n + 1) + rc->pre*(lc->n + 1);
		sum = lc->sum + rc->sum + v;
		n = lc->n + rc->n + 1;
	}

	void down()
	{
		Node* &lc = ch[0], * &rc = ch[1];
		if (rev) {
			lc->reverse();
			rc->reverse();
			rev = false;
		}
		if (d) {
			lc->add(d);
			rc->add(d);
			d = 0;
		}
	}

	void setf(Node* f, int t1)
	{
		t = t1;
		fa = f;
		t >= 0 ? f->ch[t] = this : 0;
	}
} nodes[N + 1], * nil = nodes;

Node::Node(): fa(nil), ss(0), pre(0), suf(0), sum(0), v(0), n(0), d(0), t(-1), rev(false)
{
	ch[0] = ch[1] = nil;
}

void Node::add(int a)
{
	if (this == nil) return;
	d += a;
	v += a;
	sum += n * a;
	ss += (ull)n*(n+1)*(n+2)/6*a;
	ull tmp = (ull)n*(n+1)/2*a;
	pre += tmp;
	suf += tmp;
}

inline void rot(Node* y)
{
	Node* x = y->fa;
	int t = y->t;
	y->setf(x->fa, x->t);
	y->ch[t^1]->setf(x, t);
	x->setf(y, t^1);
	x->up();
}

void splay(Node* x)
{
	static Node* S[N];
	int top = 0;
	Node* y;
	for (y = x; y->t >= 0; y = y->fa) S[top++] = y;
	for (y->down(); top; S[--top]->down()) ;

	while (x->t >= 0) {
		if ((y = x->fa)->t >= 0)
			rot(x->t ^ y->t ? x : y);
		rot(x);
	}
	x->up();
}

void access(Node* x)
{
	for (Node* y = nil; x != nil; y = x, x = x->fa) {
		splay(x);
		x->ch[1]->t = -1;
		y->setf(x, 1);
		x->up();
	}
}

inline void make_root(Node* x)
{
	access(x);
	splay(x);
	x->reverse();
}

inline void link(Node* x, Node* y)
{
	make_root(x);
	x->setf(y, -1);
}

Node* get_root(Node* x)
{
	//access(x);
	//splay(x);
	while (x->ch[0] != nil) {
		x = x->ch[0];
		x->down();
	}
	return x;
}

ull gcd(ull a, ull b)
{
	return b ? gcd(b, a%b) : a;
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	For (i, 1, n) {
		int a;
		scanf("%d", &a);
		Node &x = nodes[i];
		x.v = x.sum = x.ss = x.pre = x.suf = a;
	}
	Rep (i, 0, n-1) {
		int u, v;
		scanf("%d%d", &u, &v);
		link(nodes + u, nodes + v);
	}
	while (m--) {
		int op, u, v, d;
		scanf("%d%d%d", &op, &u, &v);
		if (op == 3)
			scanf("%d", &d);

		Node* x = nodes + u, * y = nodes + v;
		make_root(x);
		access(y);
		splay(y);
		if (op == 1) { // cut
			if (y->n == 2) {
				y->ch[0] = x->fa = nil;
				x->t = -1;
				y->up();
			}
		} else if (get_root(y) == x) {
			if (op == 3) // add
				y->add(d);
			else if (op == 4) { // query
				ull t = (ull)y->n*(y->n + 1)/2, g = gcd(y->ss, t);
				printf("%llu/%llu\n", y->ss/g, t/g);
			}
		} else if (op == 2) // link
			link(x, y);
		else if (op == 4) // query
			puts("-1");
	}

	return 0;
}