コンテンツにスキップ

ABC479 E - Larger Component

サイト
AtCoder
コンテスト
ABC479
問題
E - Larger Component
難易度
-

NN 頂点の木があり、辺 ii は頂点 AiA_i と BiB_i を結びます(NN は奇数)。各 i=1,…,N−1i = 1, \dots, N - 1 について、辺 ii を取り除いてできる 2 つの連結成分のうち、頂点数が多い方のすべての頂点 vv の xvx_v に ii を足します。最終的な x1,…,xNx_1, \dots, x_N を求める問題です(3≤N≤2×105−13 \le N \le 2 \times 10^5 - 1)。

頂点 11 を根とする根付き木で考えます。辺 ii が親 uu と子 vv を結ぶとき、辺 ii を取り除いてできる連結成分は「vv の部分木」と「それ以外」です。vv の部分木の頂点数 szv\mathrm{sz}_v は、葉の側から足し合わせれば全頂点について O(N)O(N) で求められます。

  • 2 szv>N2 \, \mathrm{sz}_v > N なら、vv の部分木の全頂点に ii を足します。
  • そうでなければ、vv の部分木以外の全頂点に ii を足します。これは「全頂点に ii を足し、vv の部分木の全頂点から ii を引く」と言い換えられます。

どちらも「ある頂点の部分木全体に値を足す」操作になります(全頂点は根の部分木です)。これは木の上のいもす法で処理できます。頂点 ww の部分木全体に cc を足すときは、配列の ww の位置にだけ cc を足しておきます。すべて記録したら、根から葉に向かって親の値を子に足していきます。すると、各頂点の値は根からその頂点までの経路上の記録の合計になります。これは、その頂点を部分木に含む頂点への加算の合計なので、求める xvx_v です。

計算量は O(N)O(N) です。

Python
N = int(input())
G = [[] for _ in range(N)]
for i in range(1, N):
a, b = map(int, input().split())
G[a - 1].append((b - 1, i))
G[b - 1].append((a - 1, i))
par = [-1] * N
pid = [0] * N
order = [0]
for u in order:
for v, i in G[u]:
if v != par[u]:
par[v] = u
pid[v] = i
order.append(v)
sz = [1] * N
for v in reversed(order[1:]):
sz[par[v]] += sz[v]
x = [0] * N
for v in order[1:]:
i = pid[v]
if sz[v] * 2 > N:
x[v] += i
else:
x[0] += i
x[v] -= i
for v in order[1:]:
x[v] += x[par[v]]
print(*x)

頂点 11(コード上は 0)から BFS して、order に訪問順、par[v] に親、pid[v] に親と結ぶ辺の番号を記録しています。order を逆順に見ると子が親より先に来るので、部分木のサイズ sz が求まります。最後に order の順に親の値を子に足すことで、いもす法の記録を伝えています。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
void solve() {
LL(N);
Tree<> tree(N);
tree.read();
RootedTree<> rooted(tree, 0);
vl sz(N, 1);
for (ll u : rooted.postorder) {
for (ll v : rooted.child[u]) {
sz[u] += sz[v];
}
}
vl ans(N, 0);
for (auto e : rooted.edges()) {
ll u = e.src;
ll v = e.dst;
if (rooted.depth[u] > rooted.depth[v]) {
std::swap(u, v);
}
if (sz[v] * 2 > N) {
ans[v] += e.id + 1;
} else {
ans[0] += e.id + 1;
ans[v] -= e.id + 1;
}
}
for (ll u : rooted.preorder) {
for (ll v : rooted.child[u]) {
ans[v] += ans[u];
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

RootedTree は頂点 0 を根とする根付き木で、postorder(帰りがけ順)、preorder(行きがけ順)、child、depth を持っています。各辺について深い方の端点を v とし、v が子になるようにしています。辺の番号 e.id は 0 始まりなので、11 を足しています。

使用ライブラリ:cpp_include@402f0cf