牛客竞赛题目讲解_旗鼓相当的对手(树形DP)
2022-06-22 10:45 作者:Clayton_Zhou | 我要投稿
// https://ac.nowcoder.com/acm/contest/4853/E
//使用树形DP
//运行时间(ms) 使用内存(KB) 代码长度
//844 229784 1400
//牛客竞赛题目讲解_旗鼓相当的对手(树上启发式合并)
//https://www.bilibili.com/video/BV1pL4y1F7Pc?spm_id_from=333.999.0.0
//
//使用树上启发式合并
//运行时间(ms) 使用内存(KB) 代码长度
//197 12172 1818
定义dp[u][j]为节点u为根的所有子树中长度为j的路径的条数. dp[u][0]=1 是为了后面的组合乘法
定义dpac[u][j]为节点u为根的所有子树中长度为j的路径端点权重之和. dp[u][0]= ac[u]
