customaddone
commented
2 years ago 距離 2つの頂点間の最短距離が一意に定まる 木の直経は0から最も遠い頂点をrとすると、rから最も遠い頂点までの距離 https://atcoder.jp/contests/arc022/submissions/18528908 C - ロミオとジュリエット 最短パスはO(N)で求められ、最短パス長さはO(logN)で求められる（LCA） K経由のdist(i, j) = dist(i, K) + dist(K, j) https://atcoder.jp/contests/abc070/submissions/27503717 D - Transit Tree Path グラフAに任意の本数辺を加えたグラフをBとすると、グラフA内の任意の頂点i, jの最短距離 >= グラフB内の頂点i, jの最短距離 同様に減らすと グラフAの<=グラフB スターグラフは距離1の点対がN-1個、距離2の点対が(N - 1) * (N - 2) // 2ある木グラフ ここから辺を1本増やすごとに距離2の点対が1個ずつ減っていく https://atcoder.jp/contests/abc131/submissions/27940519 E - Friendships 木上の任意の点vに他各頂点を1近づける を行うと任意の２点 a, bの距離は lca(a, b) = a or b: そのまま v = a or b: 1近づく not lca(a, b) = a or b: 2近づく https://atcoder.jp/contests/agc033/submissions/17877411 C - Removing Coins パスグラフ上の点はそれぞれ最も遠い点との距離がmax(N, N - i)の点である 最も遠い点との距離がd-1の頂点に葉を1つ加えるとその頂点と最も遠い点との距離はd https://atcoder.jp/contests/agc005/submissions/18100652 C - Tree Restoring N - sizeで全ての頂点間の総和を求められる https://atcoder.jp/contests/typical90/submissions/22556849 Tree Distance（★5） 「N頂点の木について、a-b, b-c, c-aのいずれかのパスに属する辺の数が最大になるようなa, b, cを求める」 の答えが「直径の端点a, bとパスa-bから最も遠い点c」 https://codeforces.com/contest/1294/submission/144940988 F. Three Paths on a Tree q1, q2, q3...について根から頂点uへのパスからの距離が1以内な頂点uは存在するか？ q1, q2...をそれぞれ根の方向に1ずつ遡ってそれが1本のパス（距離が0）を構成しているか ダブリングのライブラリを使う https://codeforces.com/contest/1328/submission/145003749 E. Tree Queries 木の中心はどの木の直径パスにとっても中心である 辺の真ん中に頂点を作ればいい感じになる 木の中心の子要素それぞれについてその子孫に候補となる頂点がいくつあるかを記録する https://atcoder.jp/contests/abc221/submissions/29351013 F - Diameter set 直径d,最大次数kの木の最大頂点数は r = (d+1)//2とし、k>=3のとき dが偶数の時 k((k-1)^r-1)/(k-2) +1 dが奇数の時 2((k-1)^r-1)/(k-2) いい感じに頂点N, 直径D, 最大次数Kの木を構築できる https://codeforces.com/contest/1003/submission/155571872 E. Tree Constructing
木構造とは、N頂点をN-1本の辺で閉路がなく連結につなぐグラフのことである 幅優先探索 高さ0の頂点が全て探索される→高さ1の頂点が全て探索される... https://atcoder.jp/contests/abc138/submissions/27937966 深さ優先探索 pypyでやると超遅くなる sys.setrecursionlimit(10000000)つけよう dfs(v)の実行直前と実行直後の間にvの子要素が全て探索される つまりdfsで探索した順に頂点に番号を新たに振っていくとし、頂点iに再び戻ってきた時に現在まで使用したカウンターの数をpos[i]で保持するとすると、 iの部分木の頂点:[i ~ pos[i]]になる RMQなどでいっぺんに操作すると部分木全てに操作したことになる https://atcoder.jp/contests/abc138/submissions/27938042 葉は次数が1の頂点 葉で閉じ込められる https://atcoder.jp/contests/abc148/submissions/15552564 F - Playing Tag on Tree 好きな頂点を1つ選んでそこから2つのエッジを伸ばしていくとHamiltonish Pathができる このパスは必ずできる https://atcoder.jp/contests/agc013/submissions/17640693 B - Hamiltonish Path 非再帰dfs 要するにスタック芸 https://codeforces.com/contest/1566/submission/145356639 E. Buds Re-hanging https://codeforces.com/contest/1399/submission/145353108 E1. Weights Division (easy version) https://codeforces.com/contest/1714/submission/166769384 G. Path Prefixes