\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
問題概要
有向 tree \(T\) を構成する．
- \(N := \{0, 1, \cdots, N-1\}\)
- \(|V(T)| = 2N-1\)
- The set \(L := \set{\{i\}}{ i \in N}\) is the set of leafs of T.
- For any vertex \(x\) of \(V\) is a subset of \(L\).
- There is a unique \(r \in V(T)\) such that \(r = N\). We denote that \(r\) is a root of \(T\).
- For any distinct vertices \(x\) and \(y\) with same parents such that \(x \cap y\) is the empty set.
解法
プレイヤー \(i \in N\) が，どの vertex \(in V(T)\) に属すのかを \(gp : N \rightarrow V(T)\) で表す．
\(V(T)\) に対して，代表元を決めながら合併する． \(p, q \in N\) の試合の後に新しくできる vertex を \(v \in V(T)\) とおく．
試合の後にするべき操作は，
- 頂点の更新:
- \(gp(p)\) と \(gp(q)\) のマージ．
- 代表元の更新: \(gp(leader(v)) = v\)
- 辺の更新:
- \(v \rightarrow gp(p)\), \(v \rightarrow gp(q)\) を作る．
するべき操作が決まれば，用意すべきものが決まる．
用意するものは，
- 各 \(w in V(T)\) に対する代表元
- 各 \(i \in N\) に対して，今 \(i\) が属している \(V(T)\) の元であって， 一番新しく作成されたもの．
これらは，Uinon-Find で実現できる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
UnionFind<ll> uf(n);
vll gp(n); rep(i,n) gp[i] = i;
vll sz(2*n-1,1);
vvll to(2*n-1);
rep(i,n-1){
ll p,q; cin >> p >> q;
--p, --q;
p = uf[p];
q = uf[q];
// new vertex v
ll v = i + n;
// new edges
// v -> gp[p],
// v -> gp[q]
to[v] = vll({gp[p], gp[q]});
// vertex
sz[v] = uf.size(p) + uf.size(q); // rem : not sz[uf.size(p)]
uf.merge(p,q);
gp[p] = v; // p = leader of v
}
ll root = 2*n-1 -1;
auto dfs = [&](auto dfs, ll cu) -> void {
for(ll ne : to[cu]) {
dp[ne] = dp[cu] + mint(sz[ne])/mint(sz[cu]);
dfs(dfs, ne);
}
};
dfs(dfs, root);
rep(i,n) cout << dp[i].val() << " ";
return 0;
}
