Advertisement
Guest User

Untitled

a guest
Aug 17th, 2020
570
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.61 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //Optimizations
  5. #pragma GCC optimize("Ofast")
  6. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  7.  
  8. //save time
  9. #define endl '\n'
  10. #define db(x) cerr << "> " << #x << ": " << x << endl
  11. typedef long long ll;
  12.  
  13. #define all(a) a.begin(),a.end()
  14.  
  15. #define REP(i,n) for(int i=0;i<(n);++i)
  16. #define FOR(i,a,b) for(int i=(a);i<(b);++i)
  17. #define DFOR(i,a,b) for(int i=(a);i>=(b);--i)
  18.  
  19. //vectors
  20. #define vi vector<int>
  21. #define vll vector<ll>
  22. #define pb push_back
  23. #define vb vector<bool>
  24.  
  25. #define pi pair<int,int>
  26.  
  27. #define gc getchar
  28. #define pc putchar
  29.  
  30. #define IOS ios::sync_with_stdio(false)
  31. #define TIE cin.tie(NULL);cout.tie(NULL)
  32.  
  33.  
  34. //general
  35. #define E empty()
  36.  
  37. const int MAXN=3e5+5;
  38. vi g[MAXN];
  39. int d;int n ;
  40. vector<vi> parent(32, vi(MAXN, -1));
  41. vi depth(MAXN, 0);
  42.  
  43. int lca(int i, int j){
  44. if(depth[i] < depth[j])swap(i, j);
  45. int jump = depth[i] - depth[j];
  46. // assert(jump >=0);
  47. for(int k = 0; k <=d ; ++k){
  48. if(jump& (1 << k)){
  49. i = parent[k][i];
  50.  
  51. }
  52. }
  53. if(i == j)return i;
  54. for(int k = d; k >= 0; --k){
  55. if(parent[k][i] != parent[k][j]){
  56. i = parent[k][i];
  57. j = parent[k][j];
  58. }
  59. }
  60. return parent[0][i];
  61. }
  62. int dist(int i, int j){
  63.  
  64. return depth[i] + depth[j] - 2*depth[lca(i, j)];
  65. }
  66.  
  67. int main(){
  68. IOS;
  69. TIE;
  70. cin >>n ;
  71. d= log(n)+1;
  72. REP(i, n-1){
  73. int from, to; cin >> from >> to;
  74. --from, --to;
  75. g[from].pb(to);
  76. g[to].pb(from);
  77. }
  78. queue<int> q;
  79. vb vis(n+1, 0);
  80. q.push(0);
  81. vis[0]=1;
  82. while(!q.empty()){
  83. int u = q.front();
  84. q.pop();
  85. for(auto v: g[u])if(!vis[v]){
  86. vis[v]=1;
  87. q.push(v);
  88. depth[v] =depth[u]+1;
  89. parent[0][v] = u;
  90. }
  91. }
  92. for(int k = 1; k<=d; ++k){
  93. for(int node = 0 ; node < n ; ++node){
  94. int mid = parent[k-1][node];
  95. if(mid!=-1){
  96. parent[k][node] = parent[k-1][mid];
  97. }
  98. }
  99. }
  100.  
  101.  
  102.  
  103. int r; cin >> r;
  104. while(r--){
  105. int from, to, c;
  106. cin >> from >> to >>c;
  107. --from, --to;
  108. int _dist = dist(from, to);
  109.  
  110. if(_dist <= c){
  111. cout << to+1<< endl;
  112. }
  113. else{
  114. for(int k = 0; k<= d; ++k){
  115. if(c &(1 <<k)){
  116. from = parent[k][from];
  117. }
  118. }
  119. cout << from+1 << endl;
  120. }
  121. }
  122.  
  123.  
  124. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement