fork download
copy 
  1.  
  2. #include "iostream"
  3. #include "algorithm"
  4. #include "queue"
  5. #include "string.h"
  6.  
  7. using namespace std;
  8. typedef long long int ll;
  9. vector<int> vg[2000005];
  10. bool used[2000005];
  11. ll dp[2000005];
  12.  
  13. ll myFunction(int root , int parent){
  14.    used[root] = true;
  15.    ll max1 = 0, max2 = 0;
  16.    for( int i= 0; i < vg[root].size(); i++) {
  17.       if(parent == vg[root][i]) continue;
  18.          ll x =  myFunction(vg[root][i],root) + 1;
  19.          if(x >= max1 ) {
  20.             max2 = max1;
  21.             max1 = x;
  22.          }
  23.          else max2 = max(x,max2);
  24.       }
  25.    dp[root] = max1 + max2;
  26.    return max1;
  27. }
  28.  
  29. int main(){
  30.    ios::sync_with_stdio(0);
  31.    int n ,m,u,v,query,root;
  32.    cin >> n ;
  33.    for(int i=1 ; i <= n-1 ; i++) {
  34.       cin >> u >> v ;
  35.       vg[v].push_back(u);
  36.       vg[u].push_back(v);
  37.    }
  38.    memset(used, false,sizeof(used));
  39.    memset(dp,0,sizeof(dp));
  40.    cin >> root >> query;
  41.    myFunction(root,-1);
  42.    while(query --) {
  43.       cin >> u;
  44.       cout << dp[u] <<"\n";
  45.    }
  46.    return 0;
  47. }
Success #stdin #stdout 0.28s 67580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1yYmQq
language:
C++14 (gcc 8.3)
created:
5 years 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!