Advertisement
Guest User

Untitled

a guest
Feb 18th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.92 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. const int MAXN = 1e5+100;
  4. #define lp(i,a,b) for(int i=a;i<b;i++)
  5. #define mk make_pair
  6. #define pb push_back
  7. #define LOG 20
  8. #define ff first
  9. #define ss second
  10.  
  11. using namespace std;
  12.  
  13. typedef pair<int,int> pii;
  14.  
  15. int N,K, pai[MAXN], nivel[MAXN];
  16. int resp, resp_dois;
  17. vector<pii> adj[MAXN];
  18. int dp2[MAXN][LOG], dp3[MAXN][LOG], dp[MAXN][LOG];
  19.  
  20. void ini()
  21. {
  22.     // memset(dp, -1, sizeof dp);
  23.     lp(i,0,MAXN) dp[i][0]=pai[i];
  24.     lp(j,1,LOG)
  25.         lp(i,1,N+1)
  26.             // if(dp[i][j-1]!=-1)
  27.                 dp[i][j] = dp[dp[i][j-1]][j-1];
  28.     // lp(i,1,N+1)
  29.     lp(j,1,LOG)
  30.     lp(i,1,N+1)
  31.     {
  32.         if(dp[i][j-1] == -1) {
  33.           dp2[i][j] = dp2[i][j-1];
  34.           dp3[i][j] = dp3[i][j-1];
  35.         } else {
  36.           dp2[i][j] = min(dp2[i][j-1], dp2[dp[i][j-1]][j-1]);
  37.           dp3[i][j] = max(dp3[i][j-1], dp3[dp[i][j-1]][j-1]);
  38.         }
  39.     }
  40. }
  41.  
  42. int LCA(int a, int b)
  43. {
  44.     // printf("1 RESP=%d\n", resp);
  45.     //assumindo que b está mais abaixo na arvore que a
  46.     if (nivel[a]>nivel[b]) swap(a,b);
  47.     //agora preciso nivelá-los
  48.     for(int i=LOG-1;i>=0;i--)
  49.         if(nivel[b]-(1<<i)>=nivel[a]){
  50.             resp=min(resp, dp2[b][i]);
  51.             // printf("2 RESP=%d i=%d b=%d\n", resp, i, b);
  52.             resp_dois=max(resp_dois, dp3[b][i]);
  53.             b = dp[b][i];
  54.         }
  55.  
  56.     if(a==b) return a;
  57.     for(int i=LOG-1;i>=0;i--)
  58.     {
  59.         if(dp[a][i]!=-1 and dp[a][i]!=dp[b][i])
  60.         {
  61.             resp_dois=max(resp_dois, dp3[a][i]);
  62.             resp_dois=max(resp_dois, dp3[b][i]);
  63.             resp=min(resp, dp2[a][i]);
  64.             resp=min(resp, dp2[b][i]);
  65.             // printf("3 RESP=%d\n", resp);
  66.             a = dp[a][i];
  67.             b = dp[b][i];
  68.         }
  69.     }
  70.     resp_dois=max(dp3[a][0], resp_dois);
  71.     resp_dois=max(dp3[b][0], resp_dois);
  72.     resp=min(dp2[a][0], resp);
  73.     resp=min(dp2[b][0], resp);
  74.     // printf("4 RESP=%d\n", resp);
  75.     return pai[a];
  76. }
  77.  
  78. int main()
  79. {
  80.   ios_base::sync_with_stdio(false);
  81.   cin.tie(NULL);
  82.   cin>>N;
  83.   lp(i,0,N-1)
  84.   {
  85.     int c,a,b;
  86.     cin>>a>>b>>c;
  87.     adj[a].pb(mk(b,c));
  88.     adj[b].pb(mk(a,c));
  89.   }
  90.   queue<int> fila;
  91.   fila.push(1);
  92.   // pai[1]=-1;
  93.   pai[1]=1;
  94.   nivel[1] = 0;
  95.   dp2[1][0] = 0x3f3f3f3f; //min
  96.   dp3[1][0] = 0; //max
  97.   while(!fila.empty())
  98.   {
  99.     int topo = fila.front();
  100.     fila.pop();
  101.     lp(i,0,adj[topo].size())
  102.     {
  103.       int v = adj[topo][i].first;
  104.       if(v!=pai[topo]){
  105.         pai[v] = topo;
  106.         nivel[v]=nivel[topo]+1;
  107.         dp2[v][0] = dp3[v][0] =adj[topo][i].ss;
  108.         fila.push(v);
  109.       }
  110.     }
  111.   }
  112.   // printf("dp2 3 0 = %d\n", dp2[3][0]);
  113.   ini();
  114.   cin>>K;
  115.   while(K--)
  116.   {
  117.       int a,b, lca;
  118.       cin>>a>>b;
  119.       resp=0x3f3f3f3f;
  120.       resp_dois=-1;
  121.       if(a==b)
  122.       {
  123.           cout<<"0 0"<<endl;
  124.           continue;
  125.       }
  126.       lca = LCA(a,b);
  127.       cout<<resp<<" "<<resp_dois<<endl;
  128.      
  129.   }
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement