code

mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.4 kB
3
Indexable
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

#define MOD 1000000007

#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

ll gcd ( ll a, ll b ) {    return __gcd ( a, b );}
ll lcm ( ll a, ll b ) {    return a * ( b / gcd ( a, b ) );}

const ll N = 1e5 + 123;
vector< pair<ll, ll> > graph[N];
ll depth[N];
ll mx_depth = 0, mx_node = 0;

void DFS( ll vertex, ll par = -1 )
{
    for ( auto child : graph[vertex] )
    {
        if ( child.F == par )continue;
        depth[child.F] = depth[vertex] + child.S;
        DFS(child.F, vertex);
    }
}


int main() {

        int t;
        cin >> t;

        for ( int tc = 1; tc <= t; tc++ )
        {
            //memset( depth, 0, sizeof(depth));
            memset( graph, 0, sizeof(graph));
            int node;
            cin >> node;

            for ( int i = 0; i < node - 1; i++ )
            {
                ll e1, e2, cost;
                cin >> e1 >> e2 >> cost;

                graph[e1].PB({e2, cost});
                graph[e2].PB({e1, cost});
            }
        

            DFS( 0 );

            // for ( int i = 1; i < node; i++ )
            // {
            //     cout << depth[i] << " ";
            // }

            for ( int i = 0; i < node; i++ )
            {
                if ( mx_depth < depth[i] )
                {
                    mx_depth = depth[i];
                    mx_node = i;
                }
            }
            memset( depth, 0, sizeof(depth));

            DFS( mx_node );

            for ( int i = 0; i < node; i++ )
            {
                cout << depth[i] << " ";
            }
            mx_node = 0, mx_depth = 0;

            for ( int i = 0; i < node; i++ )
            {
                if ( mx_depth < depth[i] )
                {
                    mx_depth = depth[i];
                    mx_node = i;
                }
            }
             cout << "Case " << tc << ": " << mx_node << endl;
        }

    return 0;
}