Submission #2236026
Source Code Expand
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define REFOR(i, m, n) for(int i = int(n - 1);i >= int(m);i--)
#define REP(i,n) for(int i = 0; i < int(n); i++)
#define REREP(i,n) for(int i = int(n - 1); i >= 0; i--)
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define PAIR pair<int,int>
#define MP make_pair
#define VP vector<pair<int,int>>
#define VS vector<string>
#define MAP map<int,int>
#define QUE queue<int>
#define DEQ deque<int>
#define PQUE priority_queue<int> //5,5,4,3,3,2,...
#define REPQUE priority_queue<int, vector<int>, greater<int>> //1,1,2,3,4,4,5,...
#define SUM(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SORT(obj) sort((obj).begin(), (obj).end()) // 1,2,3,4,5...
#define RESORT(obj) sort((obj).begin(), (obj).end(), greater<int>()) // 5,4,3,2,1...
#define UB(obj,n) upper_bound((obj).begin(), (obj).end(), n) //itr > n
#define LB(obj,n) lower_bound((obj).begin(), (obj).end(), n) //itr>= n
const ll MOD = (ll)1e9 + 7;
const ll INF = (ll)1e17;
int gcd(int a, int b) {
if (a == 0 || b == 0) return 0;
if (a < b) swap(a, b);
while (b != 0) {
a = a%b;
swap(a, b);
}
return a;
}
int lcm(int a, int b) {
if (a == 0 || b == 0) return 0;
return a / gcd(a, b)*b;
}
vector<bool> Eratosthenes(int N) {
vector<bool> Eratosthenes(N + 1, true);
Eratosthenes[0] = false;
if (N == 0) return Eratosthenes;
Eratosthenes[1] = false;
for (int i = 1; i*i <= N; i++) if (Eratosthenes[i]) for (int j = 2 * i; j <= N; j += i) Eratosthenes[j] = false;
return Eratosthenes;
}
bool pcheck(int N) {
if (N == 0 || N == 1) return false;
for (int i = 2; i*i <= N; i++) if (N % i == 0) return false;
return true;
}
////combination mod-------------------------------------------------------------------------
//
//vector<ll> f;//erase this line when you use!
//
////vector including modulus of N!
//vector<ll> factorial(ll N, ll quotient) {
// vector<ll> factorial(N + 1, 1);
// for (ll i = 1; i <= N; i++) {
// factorial[i] *=factorial[i - 1]*i;
// factorial[i] %= quotient;
// }
// return factorial;
//}
//
////repeat square method y = x^n mod quotient
//ll rsm(ll x,ll n,ll quotient){
// ll y = 1;
// while (n > 0) {
// if ((n & 1) == 1) {
// y *= x;
// y %= quotient;
// }
// x *= x;
// x %= quotient;
// n >>= 1;
// }
// return y;
//}
//
////modulus of nCk - combination mod
//ll nCk(ll n, ll k, ll quotient) {
//
// ll nCk = (f[n] % quotient);
// nCk *= rsm(f[k], quotient - 2, quotient);
// nCk %= quotient;
// nCk *= rsm(f[n - k], quotient - 2, quotient);
// return (nCk % quotient);
//}
////------------------------------------------------------------
////union-find---------------------------------------------------
//int node[10];
//
//int root(int n) {
// if (node[n] == n) return n;
// else return node[n] = root(node[n]);
//}
//
//void unite(int n, int m) {
// if (n > m) swap(n, m);
// n = root(n);
// m = root(m);
// if (n == m) return;
// else node[m] = n;
//}
//-------------------------------------------------------------
//void dijkstra(int start) {
// priority_queue<PAIR, vector<PAIR>, greater<PAIR>> pq;
// dist[start][start] = 0;
// pq.push({ 0,start });
// while (!pq.empty()) {
// int from = pq.top().second;
// pq.pop();
// REP(i, edge[from].size()) {
// int to = edge[from][i].first;
// if (dist[start][to] > dist[start][from] + edge[from][i].second) {
// dist[start][to] = dist[start][from] + edge[from][i].second;
// pq.push({ dist[start][from] + edge[from][i].second,to });
// }
// }
// }
//}
void ANS(bool flag) {
cout << ((flag) ? "YES" : "NO") << endl;
}
void Ans(bool flag) {
cout << ((flag) ? "Yes" : "No") << endl;
}
void ans(bool flag) {
cout << ((flag) ? "yes" : "no") << endl;
}
class lca {
public:
int node;
int MAXLOG2;
VVI edge;
VI depth;
VVI parent;
void set(int node_,int MAXLOG2_){
node = node_;
MAXLOG2 = MAXLOG2_;
edge.resize(node);
depth.resize(node);
parent.resize(node);
REP(i, node) parent[i].resize(MAXLOG2);
}
void dfs(int root, int root_from) {
depth[root] = 0;
parent[root][0] = root_from;
stack<pair<int, int>> st;
st.push({ root,root_from });
while (!st.empty()) {
int from = st.top().first;
int from_from = st.top().second;
st.pop();
REP(i, edge[from].size()) {
int to = edge[from][i];
if (to != from_from) {
depth[to] = depth[from] + 1;
parent[to][0] = from;
st.push({ to,from });
}
}
}
return;
}
void initialize(int N) {
REP(k, MAXLOG2 - 1) {
REP(i, N) {
if (parent[i][k] < 0) parent[i][k + 1] = -1;
else parent[i][k + 1] = parent[parent[i][k]][k];
}
}
return;
}
//get least common ancestor
int get(int a, int b) {
if (depth[a] > depth[b]) swap(a, b);
REP(k, MAXLOG2 - 1) if (((depth[b] - depth[a]) >> k) & 1) b = parent[b][k];
if (a == b) return a;
REREP(k, MAXLOG2) {
if (parent[a][k] != parent[b][k]) {
a = parent[a][k];
b = parent[b][k];
}
}
return parent[a][0];
}
};
int main() {
int N;
cin >> N;
lca T;
T.set(N, 20);
REP(i, N - 1) {
int x, y;
cin >> x >> y;
x--; y--;
T.edge[x].push_back(y);
T.edge[y].push_back(x);
}
T.dfs(0, -1);
T.initialize(N);
int Q;
cin >> Q;
VI a(Q), b(Q);
REP(i,Q) cin >> a[i] >> b[i];
REP(i,Q){
a[i]--; b[i]--;
int c = T.get(a[i], b[i]);
cout << T.depth[a[i]] + T.depth[b[i]] - 2 * T.depth[c] + 1 << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
ningenMe |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
6146 Byte |
Status |
AC |
Exec Time |
403 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 |
1 ms |
256 KB |
subtask0_sample02.txt |
AC |
1 ms |
256 KB |
subtask0_sample03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
91 ms |
17792 KB |
subtask1_02.txt |
AC |
92 ms |
17792 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
2 ms |
384 KB |
subtask1_06.txt |
AC |
2 ms |
384 KB |
subtask1_07.txt |
AC |
122 ms |
17920 KB |
subtask1_08.txt |
AC |
126 ms |
17920 KB |
subtask1_09.txt |
AC |
126 ms |
17920 KB |
subtask1_10.txt |
AC |
133 ms |
17920 KB |
subtask1_11.txt |
AC |
136 ms |
17792 KB |
subtask1_12.txt |
AC |
129 ms |
17792 KB |
subtask2_01.txt |
AC |
304 ms |
19328 KB |
subtask2_02.txt |
AC |
305 ms |
19200 KB |
subtask2_03.txt |
AC |
194 ms |
1280 KB |
subtask2_04.txt |
AC |
204 ms |
1280 KB |
subtask2_05.txt |
AC |
218 ms |
1536 KB |
subtask2_06.txt |
AC |
215 ms |
1536 KB |
subtask2_07.txt |
AC |
360 ms |
19072 KB |
subtask2_08.txt |
AC |
366 ms |
18944 KB |
subtask2_09.txt |
AC |
383 ms |
18944 KB |
subtask2_10.txt |
AC |
402 ms |
19072 KB |
subtask2_11.txt |
AC |
403 ms |
19072 KB |
subtask2_12.txt |
AC |
403 ms |
19072 KB |