ABC173 F - Intervals on Tree (600)
最初の方針
それぞれの点についてその点が単独になるLRの範囲がその点を端とする辺から考えられる
足すと答えになりそう
2,2,2に分割のようなパターンなどで当然駄目
解説の方針
木の場合は$ 辺の数 = 点の数 - 1
連結成分が1つ増えると辺は1つ減る!
それぞれの点と辺で使われる回数をカウントしてそれぞれ足して引けば良い
点はその点の番号がL以上R以下の場合に使われる
辺は両端の小さい方の番号がL以上で大きい方の番号がR以下の場合に使われる
使われる回数の計算は$ O(1)でできるので全体で$ O(N)