fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const long long N=1e5+3,big=1e18,mod=1e9+7;
  5.  
  6. vector<long long  > a[N];
  7. long long depth[N],parent[N][18],dist[N][18];
  8. long long n,x,w,y;
  9.  
  10. void dfs(long long i,long long p)
  11. {
  12.     for(int j=0;j<a[i].size();j++)
  13.         if(a[i][j]!=p)
  14.         {
  15.             parent[a[i][j]][0]=i;
  16.             depth[a[i][j]]=depth[i]+1;
  17.             dist[a[i][j]][0]=a[i][j];
  18.             dfs(a[i][j],i);
  19.         }
  20. }
  21. int main()
  22. {
  23.     cin>>n;
  24.     for(int i=0;i<n-1;i++)
  25.     {
  26.         cin>>x>>y>>w;
  27.         a[x].push_back(y);
  28.         a[y].push_back(x);
  29.     }
  30.     memset(parent,-1,sizeof(parent));
  31.     memset(dist,-1,sizeof(dist));
  32.     dfs(1,0);
  33.     for(int j=0;j<=17;j++)
  34.         parent[1][j]=-1;
  35.  
  36.     for(int j=1;j<18;j++)
  37.         for(int i=2;i<=n;i++)
  38.             {
  39.                 parent[i][j]=parent[parent[i][j-1]][j-1];
  40.                 if(parent[i][j]>=1)
  41.                 dist[i][j]=dist[parent[i][j-1]][j-1]+dist[i][j-1];
  42.             }
  43. for(int i=1;i<=n;i++)
  44. 	cout<<parent[i][0]<<" "<<parent[i][1]<<" "<<parent[i][2]<<endl;
  45.  
  46.  
  47. }
  48.  
Success #stdin #stdout 0s 46488KB
comments (?)
stdin
copy 
4
1 3
1 2 
2 4
stdout
copy 
-1 -1 -1
-1 -1 -1
1 -1 -1
-1 -1 -1
https://ideone.com/BJBawG
language:
C++ (gcc 8.3)
created:
4 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!