八倍经验！题解：AT_abc348_e [ABC348E] Minimize Sum of Distances
f_hxr_
·
·
题解
锣鼓传送门 AT 传送门
双倍经验
三倍经验
四倍经验
五倍经验
六倍经验
七倍经验
八倍经验
先考虑暴力做法。
如何求出结点 i 的答案呢？显然可以直接从结点 i 开始 DFS 一遍就行。
这样的时间复杂度为 O(N^2)。怎么优化呢？
请看下面这张图片：
定义 size_u 表示 u 的子树内所有结点的 C 的和，ALL 为所有结点的 C 的和。
如图，假设钦定 0 为根节点，并已经计算出了以 0 为根节点的答案，现在该如何计算以 2 为根节点的答案呢？
我们发现，整棵树可以分成两部分，一部分是 2 的子树，我们叫它 A，即蓝框框起来的地方。剩下的一部分我们叫它 B，也就是用黄框框起来的地方。
我们注意到，A 部分的每个结点到结点 2 的距离，正好比到结点 0 的距离多 1（显然自己到自己的距离是 0）。
由于每个结点的贡献和距离成正比。距离多 1，也就意味着答案也要增加。
增加多少呢？当然就是 A 部分的大小。即 ALL-size_2。
换句话说，ans_2=ans_0+\text{A的大小}。
上面的式子不完整，还有一个 B 呢！同理可得，由于 B 到 2 的距离比到 0 的距离要短，答案也要少一个 B。即 ans_2=ans_0+\text{A的大小}-\text{B的大小}。
这样我们通过 $ans_0$ 推出了 $ans_2$。聪明的你突发奇想，可不可以继续向下推呢？当然可以。我们也可以推出 $2$ 的儿子的答案，儿子的儿子的答案……。
等等，这个过程不就是又一个 DFS 吗？
总结一下我们的算法流程：
1. 先钦定一个结点为根，暴力预处理一遍它得答案。并求出其子树大小。
2. 然后从根节点开始 DFS，按照上面的方法递推出每个该结点的答案。
3. 取最小值即可。时间复杂度 $O(N)$。
这种方法叫“换根 DP”，也叫“二次换根与扫描法”。你也可以在各种各样的算法书上看到这类题，也算是经典咏流传了。~~不然为什么有八倍经验。~~
[AC ](https://www.luogu.com.cn/record/154736491)代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
const long long inf=1e20+7;
int N;
long long f[maxn],dep[maxn],sz[maxn],ALL,coin[maxn];
int head[maxn<<1],nxt[maxn<<1],to[maxn<<1],cnt_edge;
void AddEdge(int u,int v)
{nxt[++cnt_edge]=head[u];to[cnt_edge]=v;head[u]=cnt_edge;}
void dfs(int u,int fa,long long dep){
f[1]+=coin[u]*dep;sz[u]=coin[u];
for(int i=head[u];i;i=nxt[i]){
int v=to[i];if(v==fa)continue;
dfs(v,u,dep+1);sz[u]+=sz[v];
}
}
void solve(int u,int fa,long long ans){
f[u]=ans;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];if(v==fa)continue;
long long dans=ans;
dans-=sz[v];dans+=ALL-sz[v];//递推计算，你没看错，就这么简单。
solve(v,u,dans);
}
}
int main(){
scanf("%d",&N);
for(int i=1;i<N;i++)
{int a,b;scanf("%d %d",&a,&b);AddEdge(a,b);AddEdge(b,a);}
for(int i=1;i<=N;i++)scanf("%lld",&coin[i]),ALL+=coin[i];
dfs(1,0,0);solve(1,0,f[1]);
f[0]=inf;for(int i=1;i<=N;i++)f[0]=min(f[0],f[i]);
printf("%lld",f[0]);
return 0;
}
```