Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- //Optimizations
- #pragma GCC optimize("Ofast")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- //save time
- #define endl '\n'
- #define db(x) cerr << "> " << #x << ": " << x << endl
- typedef long long ll;
- #define all(a) a.begin(),a.end()
- #define REP(i,n) for(int i=0;i<(n);++i)
- #define FOR(i,a,b) for(int i=(a);i<(b);++i)
- #define DFOR(i,a,b) for(int i=(a);i>=(b);--i)
- //vectors
- #define vi vector<int>
- #define vll vector<ll>
- #define pb push_back
- #define vb vector<bool>
- #define pi pair<int,int>
- #define gc getchar
- #define pc putchar
- #define IOS ios::sync_with_stdio(false)
- #define TIE cin.tie(NULL);cout.tie(NULL)
- //general
- #define E empty()
- const int MAXN=3e5+5;
- vi g[MAXN];
- int d;int n ;
- vector<vi> parent(32, vi(MAXN, -1));
- vi depth(MAXN, 0);
- int lca(int i, int j){
- if(depth[i] < depth[j])swap(i, j);
- int jump = depth[i] - depth[j];
- // assert(jump >=0);
- for(int k = 0; k <=d ; ++k){
- if(jump& (1 << k)){
- i = parent[k][i];
- }
- }
- if(i == j)return i;
- for(int k = d; k >= 0; --k){
- if(parent[k][i] != parent[k][j]){
- i = parent[k][i];
- j = parent[k][j];
- }
- }
- return parent[0][i];
- }
- int dist(int i, int j){
- return depth[i] + depth[j] - 2*depth[lca(i, j)];
- }
- int main(){
- IOS;
- TIE;
- cin >>n ;
- d= log(n)+1;
- REP(i, n-1){
- int from, to; cin >> from >> to;
- --from, --to;
- g[from].pb(to);
- g[to].pb(from);
- }
- queue<int> q;
- vb vis(n+1, 0);
- q.push(0);
- vis[0]=1;
- while(!q.empty()){
- int u = q.front();
- q.pop();
- for(auto v: g[u])if(!vis[v]){
- vis[v]=1;
- q.push(v);
- depth[v] =depth[u]+1;
- parent[0][v] = u;
- }
- }
- for(int k = 1; k<=d; ++k){
- for(int node = 0 ; node < n ; ++node){
- int mid = parent[k-1][node];
- if(mid!=-1){
- parent[k][node] = parent[k-1][mid];
- }
- }
- }
- int r; cin >> r;
- while(r--){
- int from, to, c;
- cin >> from >> to >>c;
- --from, --to;
- int _dist = dist(from, to);
- if(_dist <= c){
- cout << to+1<< endl;
- }
- else{
- for(int k = 0; k<= d; ++k){
- if(c &(1 <<k)){
- from = parent[k][from];
- }
- }
- cout << from+1 << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement