算法：HDU 4679 Terrorist’s destroy（树形dp | 多校8）

算法：HDU 4679 Terrorist’s destroy（树形dp | 多校8）2014-01-01 csdn shuangde800题意

给一棵树，每条边有个权值，要删掉一条边，删掉以后会变成两颗子树，设两个子树的直径分别为d1, d2，删掉的这条边权值为w

问删掉哪一条边，使得w*max（d1, d2）的值最小？

思路

典型的树形dp, 但比赛时的代码写得非常搓，200+行，还好1A了

f（u, 0）：以u点为顶点的子树的直径

f （u, 1）：以u的父节点为顶点减去u的子树部分的子树的直径

先用树形dp求出上面的数组

然后答案等于 min{ w（u,v）*max{f（v,0）, f（v,1）} | v为u的子节点 }