N 頂点の木があり、辺 i は頂点 Ai と Bi を結びます(N は奇数)。各 i=1,…,N−1 について、辺 i を取り除いてできる 2 つの連結成分のうち、頂点数が多い方のすべての頂点 v の xv に i を足します。最終的な x1,…,xN を求める問題です(3≤N≤2×105−1)。
頂点 1 を根とする根付き木で考えます。辺 i が親 u と子 v を結ぶとき、辺 i を取り除いてできる連結成分は「v の部分木」と「それ以外」です。v の部分木の頂点数 szv は、葉の側から足し合わせれば全頂点について O(N) で求められます。
2szv>N なら、v の部分木の全頂点に i を足します。
そうでなければ、v の部分木以外の全頂点に i を足します。これは「全頂点に i を足し、v の部分木の全頂点から i を引く」と言い換えられます。
どちらも「ある頂点の部分木全体に値を足す」操作になります(全頂点は根の部分木です)。これは木の上のいもす法で処理できます。頂点 w の部分木全体に c を足すときは、配列の w の位置にだけ c を足しておきます。すべて記録したら、根から葉に向かって親の値を子に足していきます。すると、各頂点の値は根からその頂点までの経路上の記録の合計になります。これは、その頂点を部分木に含む頂点への加算の合計なので、求める xv です。