备战蓝桥杯---动态规划的一些思想2

话不多说，直接看题：

1.换根DP：

我们肯定不能对每一个根节点暴力求，我们不妨先求f[1]，我们发现当他的儿子作为根节点时深度和为f[1]+(n-cnt[i])-cnt[i](cnt[i]表示以i为根的节点数），这样子两遍DFS即可，下面是AC代码：

#include
using namespace std;
int n,x,y,cnt[1000020],dep[1000010];
long long f[1000010];
vector edge[1000010];
void dfs1(int root,int fa){
    cnt[root]=1;
    for(int i=0;in;
    for(int i=1;i