Submission #1590979
Source Code Expand
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class EulerTour {
public:
int N, k;
vector<int> g[100001]; // maxの頂点数は適宜変更
vector<int> vs, id, depth;
EulerTour (int N) : N(N), k(0), vs(2 * N - 1), id(N, -1), depth(2 * N - 1) {}
EulerTour () {}
void Init(int n) {
N = n;
k = 0;
vs.resize(2 * N - 1);
id.resize(N, -1);
depth.resize(2 * N - 1);
}
void AddEdge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
// v : vertex, d : depth, k : num
void Dfs(int v, int d, int &k) {
id[v] = k;
vs[k] = v;
depth[k++] = d;
int size_ = g[v].size();
for (int i = 0; i < size_; ++i) {
if (id[g[v][i]] == -1) {
Dfs(g[v][i], d + 1, k);
vs[k] = v;
depth[k++] = d;
}
}
}
// 根は頂点0としている
void Solve(int root = 0) {
Dfs(root, 0, k);
}
};
template <typename T>
class SegmentTree {
private:
int n;
T _init;
vector<T> seg;
int size (int N) {
int ret;
for (ret = 1; ret < N; ret <<= 1);
return ret;
}
T query(int a, int b, int k, int l, int r) {
if (r <= a or b <= l) return _init;
if (a <= l and r <= b) return seg[k];
T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
public:
SegmentTree (int N, T i = 0) : n(size(N)), seg(size(N) * 2, i), _init(i) {}
SegmentTree () {}
void Init(int N, T i) {
n = size(N);
seg.resize(size(N) * 2 - 1, i);
_init = i;
}
void Update (int k, T val) {
k += n - 1;
seg[k] = val;
while (k > 0) {
k = (k - 1) / 2;
// 適宜変更
seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
}
}
// [l, r) 開区間であることに注意!!! ... [l, r]ならfind(l, r + 1)
T Find(int l, int r) {
return query(l, r, 0, 0, n);
}
};
class LCA {
public:
int N;
EulerTour etour;
SegmentTree<pair<int, int> > segtree;
LCA() {}
LCA(int N) : N(N), etour(N) {}
void Init(int N) {
etour.Init(N);
}
void AddEdge(int u, int v) {
etour.AddEdge(u, v);
}
// LCA求める前の下準備
void Preparation() {
etour.Solve();
segtree.Init(etour.k, {int(1e9+7), int(1e9+7)});
for (int i = 0; i < etour.k; ++i) segtree.Update(i, {etour.depth[i], i});
}
int Lca(int a, int b) {
if (etour.id[a] > etour.id[b]) swap(a, b);
pair<int, int> lca = segtree.Find(etour.id[a], etour.id[b] + 1);
return etour.vs[lca.second];
}
int Solve(int a, int b) {
if (etour.id[a] > etour.id[b]) swap(a, b);
int lca = Lca(a, b), da, db, dc;
da = etour.depth[etour.id[a]];
db = etour.depth[etour.id[b]];
dc = etour.depth[etour.id[lca]];
return (da + db - 2 * dc + 1);
}
};
int N, x, y, q, a, b;
LCA lca;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N;
lca.Init(N);
for (int i = 0; i < N - 1; ++i) {
cin >> x >> y;
x--, y--;
lca.AddEdge(x, y);
}
lca.Preparation();
cin >> q;
for (int i = 0; i < q; ++i) {
cin >> a >> b;
a--, b--;
cout << lca.Solve(a, b) << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
otyaduke_117 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3517 Byte |
Status |
AC |
Exec Time |
336 ms |
Memory |
16128 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample01.txt |
AC |
2 ms |
2560 KB |
subtask0_sample02.txt |
AC |
2 ms |
2560 KB |
subtask0_sample03.txt |
AC |
2 ms |
2560 KB |
subtask1_01.txt |
AC |
45 ms |
15488 KB |
subtask1_02.txt |
AC |
45 ms |
15488 KB |
subtask1_03.txt |
AC |
2 ms |
2560 KB |
subtask1_04.txt |
AC |
2 ms |
2560 KB |
subtask1_05.txt |
AC |
3 ms |
2688 KB |
subtask1_06.txt |
AC |
3 ms |
2688 KB |
subtask1_07.txt |
AC |
61 ms |
11904 KB |
subtask1_08.txt |
AC |
54 ms |
11904 KB |
subtask1_09.txt |
AC |
53 ms |
11776 KB |
subtask1_10.txt |
AC |
58 ms |
11776 KB |
subtask1_11.txt |
AC |
56 ms |
11904 KB |
subtask1_12.txt |
AC |
55 ms |
11776 KB |
subtask2_01.txt |
AC |
227 ms |
16128 KB |
subtask2_02.txt |
AC |
243 ms |
16000 KB |
subtask2_03.txt |
AC |
178 ms |
2816 KB |
subtask2_04.txt |
AC |
201 ms |
2816 KB |
subtask2_05.txt |
AC |
219 ms |
2944 KB |
subtask2_06.txt |
AC |
220 ms |
3072 KB |
subtask2_07.txt |
AC |
310 ms |
12160 KB |
subtask2_08.txt |
AC |
320 ms |
12160 KB |
subtask2_09.txt |
AC |
317 ms |
12160 KB |
subtask2_10.txt |
AC |
307 ms |
12160 KB |
subtask2_11.txt |
AC |
336 ms |
12160 KB |
subtask2_12.txt |
AC |
309 ms |
12288 KB |