fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int N=1e5+5,Log=23;
  5. int n,q,anc[N][Log],mx[N][Log],level[N];vector<pair<int,int>>adj[N];
  6. void Build(int node,int parent,int cost)
  7. {
  8.     level[node]=level[parent]+1;
  9.     mx[node][0]=cost;
  10.     anc[node][0]=parent;
  11.     for(int i=1;i<Log;i++)
  12.     {
  13.         int p=anc[node][i-1];
  14.         mx[node][i]=max(mx[p][i-1],mx[node][i-1]);
  15.         anc[node][i]=anc[p][i-1];
  16.     }
  17.     for(auto [a,b]:adj[node])
  18.     {
  19.         if(a!=parent)
  20.         {
  21.             Build(a,node,b);
  22.         }
  23.     }
  24. }
  25. int kth(int node,int k)
  26. {
  27.     for(int i=Log-1;i>=0;i--)
  28.     {
  29.         if((k>>i)&1)
  30.         {
  31.             node=anc[node][i];
  32.         }
  33.     }
  34.     return node;
  35. }
  36. int MX(int node,int k)
  37. {
  38.     int ret=0;
  39.     for(int i=Log-1;i>=0;i--)
  40.     {
  41.         if((k>>i)&1)
  42.         {
  43.             ret=max(ret,mx[node][i]);
  44.             node=anc[node][i];
  45.         }
  46.     }
  47.     return ret;
  48. }
  49. int LCA(int a,int b)
  50. {
  51.     if(level[a]<level[b]) swap(a,b);
  52.     a=kth(a,level[a]-level[b]);
  53.     if(a==b) return a;
  54.     for(int i=Log-1;i>=0;i--)
  55.     {
  56.         if(anc[a][i]!=anc[b][i])
  57.         {
  58.             a=anc[a][i];
  59.             b=anc[b][i];
  60.         }
  61.     }
  62.     return anc[a][0];
  63. }
  64. int get(int a,int b)
  65. {
  66.     int lca=LCA(a,b);
  67.     a=MX(a,level[a]-level[lca]);
  68.     b=MX(b,level[b]-level[lca]);
  69.     return max(a,b);
  70. }
  71. int dis(int a,int b)
  72. {
  73.     int lca=LCA(a,b);
  74.     return level[a]+level[b]-2*level[lca];
  75. }
  76. void clear()
  77. {
  78. 	for(int i=0;i<=n;i++)
  79. 	{
  80. 		adj[i].clear();
  81. 		memset(anc[i],0,sizeof anc[i]);
  82. 		memset(mx[i],0,sizeof mx[i]);
  83. 	}
  84. }
  85. signed main()
  86. {
  87.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  88.     while(cin>>n)
  89.     {
  90.         if(n==0) return 0;
  91.         clear();
  92.         for(int i=2;i<=n;i++)
  93.         {
  94.             int a,b,c;cin>>a>>b>>c;
  95.             adj[a].push_back({b,c});
  96.             adj[b].push_back({a,c});
  97.         }
  98.         Build(1,0,0);
  99.         cin>>q;while(q--)
  100.         {
  101.             int a,b;cin>>a>>b;
  102.             cout<<get(a,b)<<'\n';
  103.         }
  104.     }
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 7328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nUHutn
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!