Submission #1696560
Source Code Expand
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
// lca根つき木の2点間をO(log n)で
// 準備にはO(nlog n)
// 使い方
// 辺の情報入れる->root = 1 -> init(V+1)
const int MAX_LOG = 20;
vector<vector<int> > G(100005);
int root; // 根
int parent[MAX_LOG][100005];
int depth[100005];
void dfs(int v, int par, int d) {
parent[0][v] = par;
depth[v] = d;
for(auto &to : G[v]) {
if(to == par) continue;
dfs(to, v, d + 1);
}
}
void init(int V) {
dfs(root, -1, 0);
// parentを初期化する
FOR(k,0,MAX_LOG-1) {
FOR(v,0,V) {
if(parent[k][v] < 0) parent[k+1][v] = -1;
else parent[k+1][v] = parent[k][parent[k][v]];
}
}
}
// uとvのLCA(初めて出会う頂点番号)を求める
int lca(int u, int v) {
// vの方が深いことにする
if(depth[u] > depth[v]) swap(u, v);
FOR(k,0,MAX_LOG) {
if(((depth[v]-depth[u])>>k)&1) {
v = parent[k][v];
}
}
if(u == v) return u;
// 二分探索
for(int k = MAX_LOG - 1; k >= 0; k--) {
if(parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N; cin >> N;
FOR(i,0,N-1) {
int x, y; cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
root = 1;
init(N+1);
int Q; cin >> Q;
FOR(i,0,Q) {
int a, b; cin >> a >> b;
cout << depth[a] + depth[b] - 2 * depth[lca(a, b)] + 1 << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
nenuon |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1925 Byte |
Status |
AC |
Exec Time |
312 ms |
Memory |
19328 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 |
5 ms |
8832 KB |
subtask0_sample02.txt |
AC |
5 ms |
8832 KB |
subtask0_sample03.txt |
AC |
5 ms |
8832 KB |
subtask1_01.txt |
AC |
36 ms |
18688 KB |
subtask1_02.txt |
AC |
36 ms |
18688 KB |
subtask1_03.txt |
AC |
5 ms |
8832 KB |
subtask1_04.txt |
AC |
5 ms |
8832 KB |
subtask1_05.txt |
AC |
5 ms |
8832 KB |
subtask1_06.txt |
AC |
5 ms |
8832 KB |
subtask1_07.txt |
AC |
50 ms |
14080 KB |
subtask1_08.txt |
AC |
42 ms |
13952 KB |
subtask1_09.txt |
AC |
53 ms |
13952 KB |
subtask1_10.txt |
AC |
48 ms |
13952 KB |
subtask1_11.txt |
AC |
47 ms |
13952 KB |
subtask1_12.txt |
AC |
50 ms |
13952 KB |
subtask2_01.txt |
AC |
215 ms |
19328 KB |
subtask2_02.txt |
AC |
220 ms |
19200 KB |
subtask2_03.txt |
AC |
186 ms |
8960 KB |
subtask2_04.txt |
AC |
195 ms |
8960 KB |
subtask2_05.txt |
AC |
201 ms |
9088 KB |
subtask2_06.txt |
AC |
202 ms |
9216 KB |
subtask2_07.txt |
AC |
283 ms |
14336 KB |
subtask2_08.txt |
AC |
284 ms |
14336 KB |
subtask2_09.txt |
AC |
293 ms |
14336 KB |
subtask2_10.txt |
AC |
293 ms |
14336 KB |
subtask2_11.txt |
AC |
312 ms |
14336 KB |
subtask2_12.txt |
AC |
297 ms |
14336 KB |