じゅぴろの日記(⋈◍＞◡＜◍)。✧♡

Educational Codeforces Round 36 - F. Imbalance Value of a Tree

問題リンク

解法

$I(x, y) = max(x, y) - min(x, y)$ であるので、

$\displaystyle\sum _ {i = 1} ^ {n} \sum _ {j = i} ^ {n} I(i, j) = \sum _ {i = 1} ^ {n} \sum _ {j = i} ^ {n} max(i, j) - \sum _ {i = 1} ^ {n} \sum _ {j = i} ^ {n} min(i, j)$

となり最大値と最小値を独立に考えられるので、あとは個別に数え上げよう

提出コード

まとめ

こういう分離して考えるのは典型だね