学习心得 - 动态规划 - 换根 DP
ExFish
·
·
算法·理论
题目
求树上一个点到其他点距离之和模 10^9+7。
即设 \operatorname{dis}(u,v) 为两点距离，求 f_u=\sum_{v=1}^n \operatorname{dis}(u,v) \bmod 10^9+7。
### 举例
我们首先用一个大家都会的方法处理出 $f_1$ 的答案。
考虑用 $sz$ 维护一个点的**子树大小**。
这时就可以推出 $f_p=\sum(sz_v +f_v)$（子树答案全体贡献 $+1$）
接下来我们要试图通过 $f_1$ 求出其他的答案。
我们先把根换做 $2$：
我们发现：
部分节点的贡献发生了**变化！**
注意到 $-1$ 部分的是**原来 $2$ 节点的子树。**
而**其他的点贡献全部 $+1$。**
那么，我们就得出：$f_v=f_p-sz_p+(n-sz_p)$。
化简得 $f_v=f_p-2\times sz_p+n$。
### 代码
```cpp
int sz[N];
ll f[N];
vector<int>e[N];
void dfs(int p,int fa){
sz[p]=1;
for(auto v:e[p])if(v!=fa){
dep[v]=dep[p]+1;
dfs(v,p);
(f[p]+=sz[v]+f[v])%=P;
sz[p]+=sz[v];
}
}
void dfs2(int p,int fa){
for(auto v:e[p])if(v!=fa){
f[v]=(f[p]-2*sz[v]+n)%P;
dfs2(v,p);
}
}
```
第一次求 $f_1$，$sz$，第二次求 $f_{2\dots n}$。