自动搬运

查看原文

来自洛谷，原作者为

	Wen_kr 谢谢你。

搬运于2025-08-24 22:04:30，当前版本为作者最后更新于2018-12-03 09:53:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

很有意思的一道题，看到还没有人发布题解我就发了...

ps : PoPoQQQ dalao Orz

涉及 Link 和 Cut,我们考虑使用 LCT。

对于一条路径：

$a_1a_2a_3a_4\dots a_n$

我们定义 $a_i$ 为这条路径上第 $i$ 个点的点权 (题目上的美丽程度)

那么设 $exp$ 表示这条路径的期望，那么 $exp = \frac{a_1*1*n+a_2*2*(n-1)+a_3*3*(n-2)+\dots+a_n*n*1}{C_n^2}$

(洛咕不能用 cfrac 字体有点小，见谅)

这个式子怎么得来的呢？

我们首先考虑子路径条数，显然这个数字等于 $C_n^2$

对于第 $i$ 个点的权值 $a_i$，它显然会被 $i * (n - i + 1)$ 条路径覆盖(从 $i$ 及 $i$ 的左边选择左端点，从 $i$ 及 $i$ 的右边选择右端点)。

于是第 $i$ 个点最后产生的贡献就是 $a_i * i * (n - i + 1)$

这些贡献累加起来就成了我们的分子。

分母我们在 $split$ 之后只需要 $sz$ 即可简单地算出，我们考虑在 $splay$ 每个节点中维护分子。

怎样进行维护呢，我们考虑一条跨过根节点的路径长这样：

a_1 --- a_2 --- a_3 --- a_4(根节点) --- a_5 --- a_6

$\ \ \ \ \ \ \$左子树$\qquad\qquad\qquad\qquad$ 右子树

此时根节点部分维护的分子为 $a_1*1*6+a_2*2*5+a_3*3*4+\dots+a_6*6*1$

左子树维护的分子为

$a_1*1*3+a_2*2*2+a_3*3*1$

左子树对当前节点的贡献应当为：

$a_1*1*6+a_2*2*5+a_3*3*4$

考虑两者做差，得到：

$a_1*1*3+2_2*2*3+a_3*3*3 = 3*(a_1+2a_2+3a_3)$

观察发现，外面的这个 $3$ 恰好等于右子树的大小 + 1

我们设 $lsum = a_1 * 1 + a_2 * 2 + a_3 * 3 + \dots + a_n * n$

则左子树对答案的贡献为 $exp_{lc}+lsum_{lc} * (sz_{rc}+1)$

同理，我们设 $rsum = a_1 * n + a_2 * (n - 1) + \dots + a_n * 1$

那么右子树对答案的贡献为 $exp_{rc}+rsum_{rc} * (sz_{lc} + 1)$

还有根节点对答案的贡献，这个很好计算，就是：

$val_{rt}*(sz_{lc}+1)*(sz_{rc}+1)$

根节点的期望就可以计算了： $exp_{rt} = exp_{lc}+exp_{rc}+val_{rt}*(sz_{lc}+1)*(sz_{rc}+1)+$ $lsum_{lc} * (sz_{rc}+1)+rsum_{rc} * (sz_{lc} + 1)$

$lsum,rsum$ 也很好维护。

我们设 $sum$ 表示当前子树内所有节点的权值和，那么

$lsum = lsum_{lc} + lsum_{rc} + sum_{rc} * (sz_{lc} + 1) + val_{rt} * (sz_{lc}+1)$

$rsum = rsum_{rc} + rsum_{lc} + sum_{lc} * (sz_{rc} + 1) + val_{rt} * (sz_{rc}+1)$

这样，我们就解决了这个问题的一半：区间 $Query$

---

我们现在考虑更新。

假设我们给某个节点的子树的所有节点权值加上 $p$

那么显然地，

$sum_{rt} = sum_{rt} + p * sz_{rt}$

$lsum_{rt} = lsum_{rt} + p * \frac{sz_{rt}*(sz_{rt}+1)}{2}$

$rsum_{rt}$ 与 $lsum_{rt}$ 相同。

$val_{rt} = val_{rt} + p$

然而 $exp_{rt}$ 就很蛋疼了。

我们设 $n = sz_{rt}$

则$exp_{rt} = exp_{rt} + p * (1 * n + 2 * (n - 1) + \dots + n * 1)$

考虑重写 $p$ 后面那一部分，我们能得到：

$(1 + 2 + 3 + \dots + n) * n - (1 * 2 + 2 * 3 + \dots + (n - 1) * n)$

前一部分很好化简，后面那一部分可以写成：

$1^2+2^2+3^2+\cdots+(n-1)^2+1+2+\dots+(n-1)$

根据小学奥数，这后半个式子整个等于:

$\frac{n * (n + 1)}{2} * n - \frac{1}{6}*(n-1)*n*(2n-1)-\frac{n*(n-1)}{2}$

然后开始化简，步骤如下:

$$\frac{n^3+n^2}{2}-\frac{2n^3-2n^2-n^2+n}{6}-\frac{n^2-n}{2} $$$$\frac{3n^3+3n}{6}-\frac{2n^3-2n^2-n^2+n}{6}$$ $$\frac{n^3+3n^2+2n}{6}$$ $$\frac{n(n^2+3n+2)}{6}$$ $$\frac{n(n+1)(n+2)}{6}$$

这样我们就得到了更新的方法。

另外的，这道题 $Push\_Down$ 必须当场 $Push\_Down$,否则会出问题(因为我们需要调用 $lsum$ 和 $rsum$

最后，代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int son[50050][2],fa[50050],sz[50050];
long long lsum[50050],val[50050],rsum[50050],EXP[50050],sum[50050],upd_tag[50050];
int rev_tag[50050];

void Push_Up(int rt)
{
	sum[rt] = val[rt] + sum[son[rt][0]] + sum[son[rt][1]];
	sz[rt] = 1 + sz[son[rt][0]] + sz[son[rt][1]];
	lsum[rt] = lsum[son[rt][0]] + val[rt] * (sz[son[rt][0]] + 1) + lsum[son[rt][1]] + sum[son[rt][1]] * (sz[son[rt][0]] + 1);
	rsum[rt] = rsum[son[rt][1]] + val[rt] * (sz[son[rt][1]] + 1) + rsum[son[rt][0]] + sum[son[rt][0]] * (sz[son[rt][1]] + 1);
	EXP[rt] = EXP[son[rt][0]] + EXP[son[rt][1]] + val[rt] * (sz[son[rt][0]] + 1) * (sz[son[rt][1]] + 1) +
	          lsum[son[rt][0]] * (sz[son[rt][1]] + 1) + rsum[son[rt][1]] * (sz[son[rt][0]] + 1);
}

void Rev(int rt)
{
	swap(son[rt][0],son[rt][1]);
	swap(lsum[rt],rsum[rt]);
	rev_tag[rt] ^= 1;
}

void Add(int rt,int valx)
{
	long long val1 = (sz[rt] * 1ll * (sz[rt] + 1)) / 2,val2 = (sz[rt] * 1ll * (sz[rt] + 1) * (sz[rt] + 2)) / 6;
	sum[rt] += valx * 1ll * sz[rt];
	val[rt] += valx;
	lsum[rt] += val1 * valx;
	rsum[rt] += val1 * valx;
	EXP[rt] += valx * val2;
	upd_tag[rt] += valx;
}

void Push_Down(int rt)
{
	if(rev_tag[rt])
	{
		Rev(son[rt][0]);
		Rev(son[rt][1]);
		rev_tag[rt] = 0;
	}
	if(upd_tag[rt])
	{
		Add(son[rt][0],upd_tag[rt]);
		Add(son[rt][1],upd_tag[rt]);
		upd_tag[rt] = 0;
	}
}

void Down(int rt)
{
	if(fa[rt]) Down(fa[rt]);
	Push_Down(rt);
}

bool is_root(int rt)
{
	return (son[fa[rt]][0] != rt && son[fa[rt]][1] != rt) || rt == 0;
}

void rotate(int rt)
{
	int f = fa[rt],g = fa[f];
	int way = son[f][1] == rt;
	if(!is_root(f)) son[g][son[g][1] == f] = rt;
	fa[rt] = g; son[f][way] = son[rt][way ^ 1];
	if(son[rt][way ^ 1]) fa[son[rt][way ^ 1]] = f;
	son[rt][way ^ 1] = f; fa[f] = rt;
	Push_Up(f); Push_Up(rt);
}

void splay(int rt)
{
	Down(rt);
	while(!is_root(rt))
	{
		int f = fa[rt],g = fa[f];
		if(!is_root(f)) (son[f][1] == rt) ^ (son[g][1] == rt) ? rotate(rt) : rotate(f);
		rotate(rt);
	}
}

void Access(int u)
{
	for(int v = 0;u;v = u,u = fa[u])
	{
		splay(u);
		son[u][1] = v;
		Push_Up(u);
	}
}

void make_root(int u)
{
	Access(u); splay(u); Rev(u);
}

int find_root(int u)
{
	Access(u); splay(u);
	while(son[u][0]) u = son[u][0];
	return u;
}

long long split(int u,int v)
{
	if(find_root(u) != find_root(v)) return -1;
	make_root(u); Access(v); splay(v);
	return EXP[v];
}

void Update(int u,int v,int val)
{
	if(find_root(u) != find_root(v)) return ;
	make_root(u); Access(v); splay(v);
	Add(v,val);
}

void Link(int u,int v)
{
	if(find_root(u) == find_root(v)) return ;
	make_root(u); fa[u] = v;
}

void Cut(int u,int v)
{
	if(find_root(u) != find_root(v)) return ;
	make_root(u); Access(v); splay(v);
	if(son[u][1] || son[v][0] != u) return;
	son[v][0] = fa[u] = 0;
	Push_Up(v);
}

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

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n; ++ i) scanf("%lld",&val[i]),Push_Up(i);
	for(int i = 1;i < n; ++ i)
	{
		int u,v;
		scanf("%d%d",&u,&v); Link(u,v);
	}
	for(int i = 1;i <= m; ++ i)
	{
		int op,u,v;scanf("%d%d%d",&op,&u,&v);
		int w; if(op == 3) scanf("%d",&w);
		if(op == 1) Cut(u,v);
		else if(op == 2) Link(u,v);
		else if(op == 3) Update(u,v,w);
		else
		{
			long long tmp = split(u,v);
			if(tmp == -1) printf("-1\n");
			else
			{
				long long csz = sz[v] * (sz[v] + 1) / 2;
				long long gcdx = gcd(csz,tmp);
				printf("%lld/%lld\n",tmp/gcdx,csz/gcdx);
			}
		}
	}
}