コンテンツにスキップ

木

タグ「木」の記事 5 件

SamCoding Round 10 (Div. 4) F - Ant Colony

nn 頂点の重み付きの木が与えられ、ii 本目の辺は頂点 uiu_i と viv_i を長さ wiw_i で結んでいます。22 頂点間の距離の最大値、つまり木の直径を求める問題です(n≤2×105n \le 2 \times 10^5、1≤wi≤1091 \le w_i \le 10^9)。

木の直径は、次の手順で求められます。

  1. 適当な頂点から最も遠い頂点 uu を求める。
  2. uu から最も遠い頂点 vv を求める。uu と vv の距離が直径。

辺の重みが非負なので、重み付きでもこの方法が使えます。各頂点からの距離は DFS や BFS で求められるので、計算量は O(n)O(n) です。答えは最大で 2×105×1092 \times 10^5 \times 10^9 程度になるので、64 ビット整数で計算します。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
#include "shogo-library/graph/tree_util.hpp"
void solve() {
LL(N);
Tree<ll> tree(N);
tree.read(-1, true);
print(tree_diameter(tree));
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

tree.read(-1, true) で、頂点番号を 0 始まりにずらし、重み付きの辺として読み込んでいます。tree_diameter は上の方法で直径の長さを求める関数です。

使用ライブラリ:cpp_include@cb82602

ABC482 E - Diameter Endpoint Colors

NN 頂点の木 TT があり、頂点 vv は色 CvC_v で塗られています。同じ色で、間の距離(パスの辺の本数)が木の直径と等しい頂点の組 (u,v)(u, v)(u<vu < v)の個数を求める問題です(N≤2×105N \le 2 \times 10^5)。

直径の長さを DD とします。木の直径の中点を中心と呼ぶと、距離がちょうど DD になる組は中心を使って次のように分けられます。

  • D=2rD = 2r が偶数のとき、中心は頂点 cc です。どの頂点も cc からの距離が rr 以下なので、距離が DD になる組は、cc からの距離がどちらも rr で、パスが cc を通るもの、つまり cc の異なる隣接頂点の側(部分木)にあるものです。
  • D=2r+1D = 2r + 1 が奇数のとき、中心は辺 (c1,c2)(c_1, c_2) です。この辺を除いて c1c_1 側と c2c_2 側に分けると、距離が DD になる組は、c1c_1 側で c1c_1 からの距離が rr の頂点と、c2c_2 側で c2c_2 からの距離が rr の頂点の組です。

どちらの場合も、直径の端点になる頂点をいくつかのグループに分けると、「距離が DD になる」ことと「異なるグループに属する」ことが同値になります。偶数のときは cc の隣接頂点ごと、奇数のときは c1c_1 側と c2c_2 側の 22 つがグループです。

あとは、異なるグループにある同じ色の頂点の組を数えればよいです。グループを順に見ていき、色ごとに「それまでのグループに含まれる頂点の個数」を持っておきます。各頂点について、その色の個数を答えに足してから、グループ内の頂点をまとめて個数に加えます。

直径と中心は BFS を 22 回するなどして求められるので、全体の計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
#include "shogo-library/graph/tree_util.hpp"
#include "shogo-library/utility/vector_func.hpp"
void solve() {
LL(N);
Tree<ll> tree(N);
tree.read();
VL(C, N);
C--;
vl cnt(N);
ll ans = 0;
for (auto g : tree_diameter_endpoint_groups(tree)) {
for (ll u : g)
ans += cnt[C[u]];
for (ll u : g)
cnt[C[u]]++;
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

tree_diameter_endpoint_groups は、上の解法のとおり直径の端点をグループに分けて返す関数です。C-- で色を 0 始まりにし、cnt に色ごとの個数を持っています。

使用ライブラリ:cpp_include@cb82602

DOJ Beginner Contest 13 D - Vassals

頂点 11 を根とする NN 頂点の根付き木があり、頂点 ii (i≥2)(i \ge 2) の親は PiP_i です。各頂点 ii には容量 BiB_i があります。辺をいくつか選び、各頂点 ii に接する選んだ辺が BiB_i 本以下になるようにするとき、選べる辺の最大本数を求める問題です(2≤N≤2000002 \le N \le 200000、0≤Bi≤2000000 \le B_i \le 200000)。

葉の側から貪欲に決めます。頂点 uu を見るときには、uu の子の部分木の中の辺はすでに決まっているとして、次のようにします。

  1. uu の各子 vv について、vv の容量が残っていて、uu の容量も残っていれば、辺 (u,v)(u, v) を選びます。
  2. そのあと uu の容量が残っていれば、uu と親を結ぶ辺の候補になります。実際に選ぶかは親を見るときに決めます。

この貪欲が最適であることは、次の 2 つの入れ替えで示せます。

  • 子の部分木の中の辺を、親への辺より優先してよい。 子 vv が親への辺 (u,v)(u, v) を選ぶために、部分木の中の辺 (v,w)(v, w) をあきらめたとします。(u,v)(u, v) を外して (v,w)(v, w) を選び直しても本数は変わらず、uu の容量が 11 空くだけです。
  • 子への辺を、親への辺より優先してよい。 子への辺 (u,v)(u, v) を選べるのに、uu の容量を親への辺に使い切った最適解があるとします。親への辺を外して (u,v)(u, v) を選んでも本数は変わりません。vv の容量はほかに使い道がなく、親の容量は 11 空きます。

子どうしの間では、どの子との辺を選んでも uu の容量を 11 使うだけで、子の残りの容量はほかで使えないので、どれから選んでも同じです。

各頂点を帰りがけ順に 1 回ずつ見るだけなので、計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N);
VL(P, N - 1);
VL(B, N);
Tree<> tree(N);
rep(i, N - 1) {
tree.add_edge(i + 1, P[i] - 1);
}
RootedTree<> rooted(tree, 0);
vl dp(N);
for (ll u : rooted.postorder) {
for (ll v : rooted.child[u]) {
if (dp[v] && B[u]) {
B[u]--;
} else {
dp[v] = 0;
}
}
if (B[u] && u != rooted.root) {
dp[u] = 1;
} else {
dp[u] = 0;
}
}
print(sum(dp));
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

rooted.postorder は帰りがけ順に並べた頂点の列、rooted.child[u] は uu の子です。B[u] は子との辺を選ぶたびに減らすので、uu の残りの容量になります。

dp[u] は、uu を見終わった時点では「uu の容量が残っていて、親への辺の候補になるか」を表します。親を見たときに、その辺を選ばなかった子の dp[v] を 00 に戻すので、最後には dp[v] が「vv と親を結ぶ辺を選んだか」になり、その総和が答えです。

使用ライブラリ:cpp_include@4b58304

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

ABC478 F - Min-First Search

頂点 1,…,N1, \ldots, N の木 TT について、頂点 11 から始めて「訪問候補の集合 SS から番号が最小の頂点を取り出して訪問し、その未訪問の隣接頂点を SS に加える」ことを繰り返したときの訪問順を f(T)f(T) とします。順列 QQ (Q1=1Q_1 = 1) が与えられるので、f(T)=Qf(T) = Q となる木 TT の個数を 998244353998244353 で割った余りを求める問題です(N≤2×105N \le 2 \times 10^5)。

以下、添字を 00 始まりにして Q0=1Q_0 = 1 とします。

i≥1i \ge 1 について、QiQ_i を SS に加えたのは、QiQ_i より先に訪問された隣接頂点です。木なので、QiQ_i に隣接する頂点のうち QiQ_i より先に訪問されるものはちょうど 1 つで、これを QiQ_i の親 QkQ_k (k<ik < i) と呼ぶことにします。木は「各 i≥1i \ge 1 の親の選び方」と 1 対 1 に対応するので、条件を満たす親の選び方を数えればよいです。

QkQ_k を訪問した時点で QiQ_i が SS に入り、QiQ_i は ii 番目に取り出されるまで SS に残ります。その間に取り出される Qk+1,…,Qi−1Q_{k+1}, \ldots, Q_{i-1} はそのときの SS の最小値なので、すべて QiQ_i より小さくなければなりません。

そこで、QiQ_i より前にある QiQ_i より大きい要素のうち最も後ろのものの位置を pip_i とします(なければ pi=0p_i = 0)。すると親の位置 kk の条件は

pi≤k≤i−1p_i \le k \le i - 1

で、選び方は i−pii - p_i 通りです(QpiQ_{p_i} 自身は大きくても、親として先に訪問されるので構いません)。

逆に、すべての ii についてこの範囲で親を選べば、ii 番目の時点で SS に残っている他の頂点 QmQ_m (m>im > i) は、親が ii より前にあるので条件から Qi<QmQ_i < Q_m となり、QiQ_i が最小として正しく取り出されます。したがって各 ii の選び方は独立で、答えは

∏i=1N−1(i−pi)\prod_{i=1}^{N-1} (i - p_i)

です。

pip_i は「直前にある自分より大きい要素の位置」なので、

  • 区間最大値のセグメント木で min_left を使って二分探索する(O(Nlog⁡N)O(N \log N))
  • 単調スタックの要領で、直前の大きい要素へのポインタをたどる(全体で O(N)O(N))

のどちらでも求められます。

C++(セグメント木)
#include "ou-library/modint.hpp"
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
using mint = modint998244353;
void solve() {
LL(N);
VL(Q, N);
Q--;
mint ans = 1;
RMaxQ<ll> seg(Q);
rep(i, 1, N) {
ll j = seg.min_left(i, [&](ll x) { return x <= Q[i]; });
if (j)
j--;
ans *= i - j;
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

min_left(i, x <= Q[i]) で「Ql,…,Qi−1Q_l, \ldots, Q_{i-1} がすべて QiQ_i 以下になる最小の ll」を求め、その 1 つ前が pip_i です。RMaxQ は区間最大値のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

cLay(ポインタをたどる)
#define MD 998244353
ll@N,@Q[N],g[N],p;mint x=1;rep(i,1,N){p=i-1;while(p&&Q[p]<Q[i])p=g[p];g[i]=p;x*=i-p;}wt(x);

g[i] に pip_i を記録しておき、Qi−1Q_{i-1} から始めて自分より小さい間は g をたどることで pip_i を求めています。Q0=1Q_0 = 1 は最小なので、より大きい要素がなければ p=0p = 0 で止まります。