fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define sz(u) (int)(u.size())
  5.  
  6. using namespace std;
  7.  
  8. const int MAXN=2e5;
  9.  
  10. int n,q;
  11. vector<vector<int>> g(MAXN);
  12. vector<int> diam, par(MAXN), ans(MAXN,-1), downMost(MAXN), preDiam(MAXN), sufDiam(MAXN);
  13. vector<bool> blocked(MAXN);
  14. int furthestNode=-1, maxDist=-1, diamL=-1;
  15.  
  16. void furthest(int u, int pr, int d=1)
  17. {
  18.     par[u]=pr;
  19.     if(d>maxDist)
  20.     {
  21.         maxDist=d;
  22.         furthestNode=u;
  23.     }
  24.     for(int v:g[u])
  25.     {
  26.         if(v==pr || blocked[v]) continue;
  27.         furthest(v,u,d+1);
  28.     }
  29. }
  30.  
  31. int findDiam(int u)
  32. {
  33.     int A=-1,B=-1;
  34.     maxDist=-1, furthestNode=-1;
  35.     furthest(u,-1);
  36.     A=furthestNode;
  37.     if(diamL!=-1) downMost[u]=maxDist;
  38.     maxDist=-1, furthestNode=-1;
  39.     furthest(A,-1);
  40.     B=furthestNode;
  41.     return B;
  42. }
  43.  
  44. int main()
  45. {
  46.     ios::sync_with_stdio(0); cin.tie(0);
  47.     cin>>n>>q;
  48.     for(int i=0;i<n-1;i++)
  49.     {
  50.         int u,v; cin>>u>>v;
  51.         u--,v--;
  52.         g[u].pb(v);
  53.         g[v].pb(u);
  54.     }
  55.     int curNode = findDiam(0);
  56.     while(curNode!=-1)
  57.     {
  58.         diam.pb(curNode);
  59.         blocked[curNode]=1;
  60.         curNode=par[curNode];
  61.     }
  62.     diamL=maxDist;
  63.     ans[diamL]=0;
  64.     ans[0]=diamL;
  65.     for(int u:diam)
  66.     {
  67.         for(int v:g[u])
  68.         {
  69.             if(blocked[v]) continue;
  70.             findDiam(v);
  71.             ans[maxDist]=max(diamL,ans[maxDist]);
  72.             ans[diamL]=max(maxDist,ans[diamL]);
  73.             downMost[u]=max(downMost[u],downMost[v]);
  74.         }
  75.     }
  76.     preDiam[0]=1, sufDiam[diamL-1]=1;
  77.     for(int i=1;i<diamL;i++) preDiam[i]=max(preDiam[i-1],i+1+downMost[diam[i]]);
  78.     for(int i=1;i<diamL;i++) sufDiam[diamL-1-i]=max(sufDiam[diamL-i],i+1+downMost[diam[diamL-1-i]]);
  79.     for(int i=0;i<diamL-1;i++) ans[preDiam[i]]=max(ans[preDiam[i]],sufDiam[i+1]),ans[sufDiam[diamL-1-i]]=max(ans[sufDiam[diamL-1-i]],preDiam[diamL-2-i]);
  80.     for(int i=diamL;i>=0;i--) ans[i]=max(ans[i],ans[i+1]);
  81.     int l1,l2;
  82.     while(q--)
  83.     {
  84.         cin>>l1>>l2;
  85.         if(ans[l1]>=l2) cout<<"YES\n";
  86.         else cout<<"NO\n";
  87.     }
  88.     return 0;
  89. }
Success #stdin #stdout 0s 11644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vNB3h9
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!