Codevs 3728 聯合權值

聯合權值

http://codevs.cn/problem/3728/

給一棵樹，然後每相距離為2的點都會産生一個聯合權值，等于Wa*Wb

問你聯合權值最大的是多少，所有聯合權值的和是多少

第一行n

n-1行 x y 表示xy連一條距離為1的邊

n個數，表示每個點的權值

最大值，和

5

1 2

2 3

3 4

4 5

1 5 2 3 10

20 74

ans1 很顯然等于某個點的最大的兒子乘以次大的兒子

ans2 = w[x] * (sum[fa[x]] - w[x]),fa[x]指的是父親節點，但是這樣會重複計算，是以直接按照dfs序去跑，計算過的就删去就好了