题解：P11477 [COCI 2024/2025 #3] 林卡树 / Stablo

· · 题解

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 移动成为 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;
}

后记

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