fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iomanip>
  3. #include<iterator>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7. #define ordered_set tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update>
  8. using namespace std;
  9. #define ll long long
  10. #define pb push_back
  11. #define all(a)  a.begin(),a.end()
  12. #define death ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  13. #define sz(x) ((int)(x).size())
  14. #define el "\n"
  15. #define basmala freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);
  16. #define int ll
  17. /****************************************************************************/
  18. int dx[] = {0,  0, 1, -1};
  19. int dy[] = {1, -1, 0,  0};
  20. int di[] = {1, 1, 1, 0, 0, -1, -1, -1};
  21. int dj[] = {1, 0, -1, 1, -1, 1, 0, -1};
  22. ll mod=998244353;
  23. const int N=1e5+4;
  24. vector<pair<int,int>>adj[N];
  25. int dist1[N],dist2[N];
  26. /****************************************************************************/
  27. void bfs(int node, int d[]){
  28.     queue<int>q;
  29.     q.push(node);
  30.     fill(d, d + N, -1);
  31.     d[node]=0;
  32.     while(sz(q)){
  33.         int curr=q.front();
  34.         q.pop();
  35.         for(auto [v,w]:adj[curr]){
  36.             if(d[v]==-1){
  37.                 d[v]=d[curr]+w;
  38.                 q.push(v);
  39.             }
  40.         }
  41.     }
  42. }
  43. /****************************************************************************/
  44. void neverland(){
  45.     int n; cin>>n;
  46.     for(int i=0;i<n;i++)
  47.         adj[i].clear();
  48.     int m=n-1;
  49.     while(m--){
  50.         int a,b,c; cin>>a>>b>>c;
  51.         adj[a].emplace_back(b,c);
  52.         adj[b].emplace_back(a,c);
  53.     }
  54.     bfs(1,dist1);
  55.     int far = max_element(dist1+1,dist1+n+1)-dist1;
  56.     bfs(far,dist1);
  57.     int far2 = max_element(dist1+1,dist1+n+1)-dist1;
  58.     bfs(far2,dist2);
  59.     for(int i=1;i<=n;i++)
  60.         cout<<max(dist1[i],dist2[i])<<" ";
  61.     cout<<el;
  62. }
  63. signed main() {
  64.     // basmala;
  65.     death;
  66.     int t=1; cin>>t;
  67.     while(t--) neverland();
  68. }
Success #stdin #stdout 0.01s 7508KB
comments (?)
stdin
copy 
1
4
1 2 3
3 2 4
3 4 5
stdout
copy 
12 9 7 12
https://ideone.com/pKmvQ5
problem EAGLE1, based on SPOJ submission 34252895 (CPP), 2025-02-27 20:29:58
language:
C++ (gcc 8.3)
created:
10 days 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!