LightOJ 1257 - Farthest Nodes in a Tree (II)

//The Solution of this problem simply easy than Lightoj 1094.
// It is just 3 DFS problem.
// To avoid TLE, you have to just take two maximum node with cost which started by node 0
// you have got first maximum node from node 0 and second maximum node from the 1st maximum node. :P
// similarly you have to take distance(cost) for 1st maximum node and 2nd maximum node
// Finally, just print the maximum cost between dist1[node] and dist2[node]

/*
Example:

for the second test case:
    0 2 20

    2 1 10

    0 3 29

    0 4 50

    from 0:
          | 0-> 0
          | 1-> 30     -----> 1st maximum node = 4
          | 2-> 20
          | 3-> 29
          | 4-> 50

    from 4: dist1[nodes]
          | 0-> 50
          | 1-> 80     -----> 2nd maximum node = 1
          | 2-> 70
          | 3-> 79
          | 4-> 0

    from 1: dist2[nodes]
          | 0-> 30
          | 1-> 0
          | 2-> 10
          | 3-> 59
          | 4-> 80

Finally: compare dist1 and dist2 for each node and print the maximum. :D

    for 0: 50
    for 1: 80
    for 2: 70
    for 3: 79
    for 4: 80

That's it !

*/

// Algorithm: DFS


#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(0)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back
#define mset(c,v) memset(c , v , sizeof c)
#define loop0(n) for(int i=0; i<n; i++)
#define loop1(n) for(int i=1; i<=n; i++)
#define mpair(x , y) make_pair(x , y)
#define all(x) x.begin(), x.end()
#define pi acos(-1.0)
#define psb push_back

typedef unsigned long long ull;
typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef vector<string>vs;
typedef map<int, int>mpii;
typedef map<string, int>mpsi;
typedef map<char, int>mpci;
typedef map<LL, LL>mpll;

const int mod = 1000007;
const int high = 30003;
const int inf = 2147483647;

vector<list<pair<int, int> > >adj(high);

LL dist1[high], dist2[high], maxcost = 0;
int visited[high];
int first_maximum_node, second_maximum_node = 0;

void CLR()
{
    for(int i=0; i<high; i++)
    {
        adj[i].clear();
        dist1[i] = 0;
        dist2[i] = 0;
    }
}

void CLRVisited()
{
    for(int i=0; i<high; i++) visited[i] = 0;
}

int DFS(int u, int fl)
{
    visited[u] = 1;

    int v = 0 , cost = 0;

    if(fl == 1)
    {
        if(maxcost < dist1[u])
        {
            maxcost = dist1[u];
            first_maximum_node = u;
        }
    }

    else if(fl == 2)
    {
        if(maxcost < dist1[u])
        {
            maxcost = dist1[u];
            second_maximum_node = u;
        }
    }

    list<pair<int,int > >::iterator it;

    for(it=adj[u].begin(); it!=adj[u].end(); ++it)
    {
        v = (*it).first;
        cost = (*it).second;

        if(!visited[v])
        {
            if(fl == 1)
            {
                dist1[v] = cost + dist1[u];
                DFS(v , 1);
            }

            else if(fl == 2)
            {
                dist1[v] = cost + dist1[u];
                DFS(v , 2);
            }

            else
            {
                dist2[v] = cost + dist2[u];
                DFS(v , 3);
            }
        }
    }
}

int main()
{
    int i , n , test, tc=0 , u , v , c;
    sf("%d", &test);
    while(test--)
    {
        CLR();
        CLRVisited();

        maxcost = 0;
        first_maximum_node = second_maximum_node = 0;

        sf("%d", &n);

        for(i=0; i<n-1; i++)
        {
            sf("%d %d %d", &u , &v , &c);

            adj[u].psb(make_pair(v , c));
            adj[v].psb(make_pair(u , c));
        }

        DFS(0 , 1); // find the first largest node from 0 initially.

        CLRVisited();
        maxcost = 0;

        for(i=0; i<n+2; i++) dist1[i] = 0;

        DFS(first_maximum_node , 2); // find the second. dist1[]

        maxcost = 0;

        //for(i=0; i<n; i++) cout << dist1[i] << "; "; cout << "\n";

        CLRVisited();

        DFS(second_maximum_node , 3); // find dist2[]

        //for(i=0; i<n; i++) cout << dist2[i] << "; "; cout << "\n";

        pf("Case %d:\n", ++tc);

        for(i=0; i<n; i++)
        {
            pf("%lld\n", max(dist1[i] , dist2[i]));
        }
    }

    return 0;
}