不用推公式直接看代码就行。

题意：

给出 x，y，保证 x 在 y 的子树内。

swap（x 的位置，z 的位置），其中 z 是 x 的直接父亲，然后求 f(y) 的值。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 5e5 + 10;

int dep[N], anc[N][25];
LL v[N], sum[N], f[N];
vector<int> G[N];

void dfs(int x, int fa){
    sum[x] = v[x];
    dep[x] = dep[fa] + 1;
    anc[x][0] = fa;
    for (int i = 1; i <= 20; i ++) {
        anc[x][i] = anc[anc[x][i - 1]][i - 1];
    }
    for (int i: G[x]){
        if (i == fa) continue;
        dfs(i, x);
        sum[x] += sum[i];
        f[x] += sum[i] + f[i]; 
    }
}

int getz(int x, int y){
    // 找到 y 的儿子中，包含 x 的那个节点
    for (int i = 20; i >= 0; i --) {
        if (dep[anc[x][i]] > dep[y]) {
            x = anc[x][i]; 
        }
    }
    return x;
}

signed main(){
	int n, Q;
	cin >> n >> Q;
    for (int i = 1; i <= n; i ++) {
    	cin >> v[i];
	}
	
	for (int i = 2; i <= n; i ++) {
        int x;
        cin >> x;
        G[x].push_back(i);
        G[i].push_back(x);
    }
    
    dfs(1,0);
    
    while (Q --) {
        int x, y;
        cin >> x >> y;
        int z = getz(x, y);  // 找到 y 的包含 x 的儿子
        LL ans = f[y] + sum[z] - sum[x] - v[x] * (dep[x] - dep[y] - 1);
        
        // x 本来对 y 的贡献是 v[x] * (dep[x] - dep[y])
		// 改变后对 y 的贡献是 v[x]
		// 变化量为  - v[x] * (dep[x] - dep[y] - 1)
		
		// z 内其他子树对 y 的贡献集体 + 1，因为距离 y 多了一个点 x
		// 变化量为 + sum[z] - sum[x]
        
        cout << ans << "\n";
    }
    return 0;
}

P11477 [COCI 2024/2025 #3] 林卡树 / Stablo - Solution

题意

给定一棵 $n$ 个节点的树，每个节点 $i$ 有点权 $v_i$。定义函数：

$$f(y)=\sum_{x\in \operatorname{subtree}(y)} \operatorname{dist}(x,y)\cdot v_x$$

其中，$\operatorname{subtree}(y)$ 表示 $y$ 的子树内所有点构成的集合（包括 $y$），$\operatorname{dist}(x,y)$ 表示 $x,y$ 之间的最短路径上的边数。换言之，$f(y)$ 是 $y$ 子树内所有点的点权乘以到 $y$ 的距离求和。

有 $q$ 次操作，每次操作给定两个节点 $x, y$，保证 $x \in \text{subtree}(y)$ 且 $x \neq y$，且每次操作独立：

• 将 $x$ 的所有儿子接到 $x$ 的父亲上；
• 将 $x$ 删掉；
• 令 $y$ 的儿子中，包含 $x$ 的为 $z$。将 $x$ 插入到 $y$ 和 $z$ 之间。
• 求出 $f(y)$。

该操作的含义其实就是将 $x$ 移动成为 $y$ 的一个儿子，并且挤下来另外一个点 $z$ 来代替它。

分析

首先可以根据这张图感受一下题目，在这个变化过程中，$(x,y,z)=(5,1,2)$，树会从上图转化为下图：

我们可以发现，对于 $f(x)$ 来说，改变的值其实不多，只有 $z$ 的子树中不包含 $x$ 的子树的部分，以及 $x$ 这个点自己的值的变化，根据这个性质，我们可以找到更改后 $f'(x)$ 与 $f(x)$ 的关系，$f(x)$ 考虑使用递归的方式求出。

推导

对于 $to\in \operatorname{subtree}(x),u\in \operatorname{subtree}(to)$，易得 $dist(u,x)=dist(u,to)+1$。

接下来，我们考虑计算 $to$ 子树对 $f(x)$ 的贡献，记 $sum[x]=\sum_{u\in \operatorname{subtree}(to)} v_u$，有

$$\begin{aligned} \text{contribution}_{to}&=\sum_{u\in \operatorname{subtree}(to)} \operatorname{dist}(u,x)\cdot v_u\\ &=\sum_{u\in \operatorname{subtree}(to)}( \operatorname{dist}(u,to)+1)\cdot v_u\\ &=\sum_{u\in \operatorname{subtree}(to)} \operatorname{dist}(u,to)\cdot v_u+\sum_{u\in \operatorname{subtree}(to)} 1\cdot v_u\\ &=f(to)+sum[to] \end{aligned}$$

接下来，考虑找到更改后 $f'(x)$ 与 $f(x)$ 的关系。首先，通过另一个方式推出 $f(x)$：

$$\begin{aligned} f(x)&=\sum_{y\in \operatorname{subtree}(x)} (dep[y]-dep[x])\cdot v_y\\ &=\sum_{y\in \operatorname{subtree}(x)} dep[y]\cdot v_y-\sum_{y\in \operatorname{subtree}(x)} dep[x]\cdot v_y\\ &=\sum_{y\in \operatorname{subtree}(x)} dep[y]\cdot v_y-dep[x]\cdot sum[x] \end{aligned}$$

根据上图，可以发现改变的值其实不多，只有 $z$ 的子树中不包含 $x$ 的子树的部分会发生 $dep\gets dep+1$，以及 $x$ 节点自身的变化。

记 $z$ 的子树除去 $x$ 的子树的部分为 $t$，则可以得到如下推导：

$$\begin{aligned} f'(x) &=\sum_{u\in \operatorname{subtree}(t)} (dep[u]+1)\cdot v_u+\sum_{u\notin \operatorname{subtree}(u)}dep[u]\cdot v_u-dep[x]\cdot sum[x]-v[x]\cdot(dep[x]-dep[y]-1)\\ &=\sum_{u\in \operatorname{subtree}(t)} dep[u]\cdot v_u+sum[t]+\sum_{u\notin \operatorname{subtree}(u)}dep[u]\cdot v_u-dep[x]\cdot sum[x]-v[x]\cdot(dep[x]-dep[y]-1)\\ &=f(x)+sum[t]-v[x]\cdot(dep[x]-dep[y]-1) \end{aligned}$$

这样，就得到了可以快速处理每次操作的方式了，求 $z$ 的方法可以使用类似 LCA 的倍增思想。

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int N=5e5+5;
int v[N],n,q,dep[N],anc[N][25],sum[N],f[N];
vector<int> e[N];

void dfs(int x,int fa){
	sum[x]=v[x];
	dep[x]=dep[fa]+1;
	anc[x][0]=fa;
	for(int i=1;i<=20;i++)
		anc[x][i]=anc[anc[x][i-1]][i-1];
	for(int i:e[x]){
		if(i==fa) continue;
		dfs(i,x);
		sum[x]+=sum[i];
		f[x]+=sum[i]+f[i]; 
	}
}

int getz(int x,int y){
	for(int i=20;i>=0;i--){
		if(dep[anc[x][i]]>dep[y])
			x=anc[x][i]; 
	}
	return x;
}

signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&v[i]);
	for(int i=2;i<=n;i++){
		int x;
		scanf("%lld",&x);
		e[x].push_back(i);
		e[i].push_back(x);
	}
	dfs(1,0);
	while(q--){
		int x,y;
		scanf("%lld%lld",&x,&y);
		int z=getz(x,y);
		cout<<f[y]+sum[z]-sum[x]-v[x]*(dep[x]-dep[y]-1)<<endl;
	}
	return 0;
}

后记

这道题很考验推式子和实现算法的能力，因此我写题解也耗时许久，每一条公式都通过手打，最终得到这篇整洁的题解。