- Lowest Common Ancestor (LCA)
- 根付き木において, ある 2 頂点 u,v の両方の先祖である頂点のうち最も深さの大きい頂点
- 二分探索できるように, あらかじめ2^k回親を辿った時に到達する頂点を計算しておくことで計算を効率化することができる(ダブリング).
- LCAが用意できれば, 2頂点(u, v)間の距離は次のように書ける:
distance(u) + distance(v) - 2 * distance(LCA(u, v))
- 木を根からDFSする時に通る頂点を並べたもの.
- 各頂点の番号について, 最初に登場するindexと最後の登場するindexの間の区間がちょうど元の木の部分木になる.
- 木を列にして扱うことができるので, セグメント木などのデータ構造が使える.
- TREEクラス.
- 初期化でオイラーツアーも用意している(eulerT).
- begin[v], end[v]はvがオイラーツアー上で最初と最後に現れるインデックス.
- 距離はlong longになりうるのでテンプレート化.
- class内にarrayを詰め込みすぎるのは許されないので, namespaceが曖昧になるやつだけclass内に入れた.
- lca計算も入れた.
- 辺の距離が指定されていない時は1を入れてdepthとdistanceを同じにしておけばいい.
typedef long long ll;
typedef std::pair<int, int> ipair;
const int MAX_V = 100010;
const int MAX_LOG_V = 17;
vector<ipair> G[MAX_V];
int parent[MAX_LOG_V][MAX_V];
int depth[MAX_V];
vector<int> eulerT;
template<class T> class TREE {
public:
int k = 0;
T distance[MAX_V];
int begin[MAX_V * 2];
int end[MAX_V * 2];
// vertex, parent, depth, distance
void dfs(int v, int p, int d, T l) {
parent[0][v] = p;
depth[v] = d;
distance[v] = l;
begin[v] = k;
eulerT.push_back(v);
k++;
for (auto& g : G[v]) {
if (g.first != p) {
dfs(g.first, v, d + 1, l + g.second);
eulerT.push_back(v);
k++;
}
}
end[v] = k;
}
void init(int V, int root) {
dfs(root, -1, 0, 0);
for (int k = 0; k + 1 < MAX_LOG_V; k++) {
for (int v = 0; v < V; v++) {
if (parent[k][v] < 0) parent[k + 1][v] = -1;
else parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
int lca(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int k = 0; k < MAX_LOG_V; k++) {
// if k th digit of depth[v] - depth[u] is 1
if ((depth[v] - depth[u]) >> k & 1) {
v = parent[k][v];
}
}
if (u == v) return u;
for (int k = MAX_LOG_V - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
T dist2(int u, int v) {
return distance[u] + distance[v] - 2 * distance[lca(u, v)];
}
};
- オイラーツアー未確認
- そのままコピペするとメモリ食うので制限にかかりそうなら適宜余計な機能を消す.
- LCAは有向木についても有効なのか?
- 有向木だと根の選び方によっては, また根をどう選んだとしても全てはたどり着けないものがあるので, よほど特殊な条件じゃないとこのまま使えることはなさそう.
- LCAは閉路検知に使えるのか?
- 有向ならトポロジカルソートを使えば良さそう.
- 無向なら単純にbfsとかですでに行ったノードに到達したら閉路ありと言えそう.
- 重み付き無向グラフの負の閉路だったらベルフォとか使えばいい.
- TREEクラス(距離入れる前)を使用
- lcaを確認した
int main() {
int N;
cin >> N;
int k;
for (int i = 0; i < N; i++) {
cin >> k;
int c;
for (int j = 0; j < k; j++) {
cin >> c;
G[i].push_back(c);
G[c].push_back(i);
}
}
TREE tree;
tree.init(N, 0);
int Q;
cin >> Q;
int u, v;
for (int q = 0; q < Q; q++) {
cin >> u >> v;
cout << tree.lca(u, v) << endl;
}
return 0;
}
- TREEクラスを使用.
-
距離の計算周りを確認.
- Kを経由という指定があるので, LCAを計算する必要なく距離をそれぞれ計算すればいい.
int main() {
int N;
cin >> N;
int a, b, c;
for (int i = 0; i < N - 1; i++) {
cin >> a >> b >> c;
a--;
b--;
G[a].push_back(ipair(b, c));
G[b].push_back(ipair(a, c));
}
int Q, K;
cin >> Q >> K;
K--;
TREE<ll> tree;
tree.init(N, K);
int u, v;
for (int q = 0; q < Q; q++) {
cin >> u >> v;
u--;
v--;
ll ans = 0;
ans += tree.distance[u] + tree.distance[v];
cout << ans << endl;
}
return 0;
}
- TREEクラスを使用.
- lcaとeuler tourの組み合わせ. というかこのページはこの問題を解くために整理した.
- 一応正しいと思われるやり方で実装したが, WAかつTLEの原因がわからず.
- TREEクラスを使用.
- 2頂点間の距離の計算を使った. いちいちrootを置き直す必要はない.
- 2頂点間の距離もクラスの中に入れてみた.
int main() {
int N;
cin >> N;
int a, b;
for (int i = 0; i < N - 1; i++) {
cin >> a >> b;
a--;
b--;
G[a].push_back(ipair(b, 1));
G[b].push_back(ipair(a, 1));
}
TREE<int> tree;
tree.init(N, 0);
int cnt = 0;
for (int i = 0; i < N; i++) {
int from1 = tree.dist2(i, 0);
int fromN = tree.dist2(i, N - 1);
if (from1 <= fromN) cnt++;
}
if (cnt > N - cnt) cout << "Fennec" << endl;
else cout << "Snuke" << endl;
return 0;
}
- TREEクラス使用.
- 根からの距離の偶奇で判断すればいい.
- 最初はグラフだと思って悩んでいたが, 木は非常にシンプル. ループはないので迷うことない.
- 実装はこちら
- TREEクラス使用.
- 問題の構成上, initのdfs中に計算を追加した. アドホックなのでクラスには入れない.
- 実装はこちら