yukicoder No.1103 Directed Length Sum (★2)

問題：No.1103 Directed Length Sum - yukicoder

解答：#516999 (C++14) No.1103 Directed Length Sum - yukicoder

解法：木DP。
dp1[p]：頂点p以下の各頂点同士のパス長合計
dp2[p]：頂点p以下の頂点数合計
dp3[p]：頂点pと頂点p以下の頂点を結ぶパス長合計
とする。遷移は以下の通り。

dp1[p] = Σ(dp1[u] + dp2[u] + dp3[u])
dp2[p] = 1 + Σdp2[u]
dp3[p] = Σ(dp2[u] + dp3[u])
Σはpの子uについての合計。