行业知识
备战蓝桥杯---动态规划的一些思想2
2026-11-09 15:46:52
来源：互联网转载
话不多说，���接看题：
1.换根DP：
我们肯定不能对每一个根节点暴力求，我们不妨先求f[1]，我们发现当他的儿子作为根节点时深度和为f[1]+(n-cnt[i])-cnt[i](cnt[i]表示以i为根的节点数），这样子两遍DFS即可，下面是AC代码：
#includeusing 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
