Light OJ 1257 – Farthest Nodes in a Tree (II)

//Unsorted Ideas:

ট্রি থেকে ফারদেস্ট নোড মানে সবার দূরবর্তী দুইটা নোডের ডিসটেন্স বের করতে হবে।

ট্র ডায়ামেটার বের করা। যেহেতু ট্রি তাই  কেমিস্ট্রির শিকলের মত সবচেয়ে বড় শিকলটা বের করতে হবে! :v

যে কোন একটা র‍্যানডম নোড থেকে বিএফেস চালায়ে শিকলের এক প্রান্ত ফিক্স করতে হবে। তারপর শিকলের এই এক প্রান্ত থেকে আরেকটা বিএফেস চালিয়ে অন্য প্রান্তের নোড বের করতে হবে।

তারপর এই দুই প্রান্ত থেকে ছাড়া বিএফেস এ ক্যালকুলেট করা ডিস্টেন্স এর মধ্য থেকে প্রত্যেক নোডের জন্য ম্যাক্সিমাম ডিসটেন্স প্রিন্ট করতে হবে। এই... শেষ... !

Code: 

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 30007

ll u,v,w,n,x,y,z;

vector<int> adj[sz], cst[sz];
bool vis[sz], vis1[sz];
int d[sz], d1[sz];

ll ex,src;

void init()
{
    REP(i,sz)
    {
        d[i] = -1, d1[i] = -1;
        vis[i] = 0, vis1[i] = 0;
    }
}

int BFS(int s)
{
    queue<int> Q;

    Q.push(s);
    vis[s] = 1;
    d[s] = 0;

    int u,v;
    int mx = 0;

    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();

        if(d[u]>mx) mx = d[u], ex = u;

        REP(i,SZ(adj[u]))
        {
            v = adj[u][i];

            if(vis[v]==0)
            {
                vis[v] = 1;
                d[v] = d[u] + cst[u][i];
                Q.push(v);
            }
        }
    }
    return ex;
}

void BFS1(int s)
{
    queue<int> Q;

    Q.push(s);
    vis1[s] = 1;
    d1[s] = 0;

    int u,v;
    int mx = 0;

    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();

        if(d1[u]>mx) mx=d[u], ex = u;


        REP(i,SZ(adj[u]))
        {
            v = adj[u][i];

            if(vis1[v]==0)
            {
                vis1[v] = 1;
                d1[v] = d1[u] + cst[u][i];
                Q.push(v);
            }
        }
    }
}

int main()
{
    ll t,cs=0;
    scl(t);
    while(t--)
    {
        scl(n);
        REP(i,n-1)
        {
            scll(x,y), scl(z);
            adj[x].pb(y);
            adj[y].pb(x);
            cst[x].pb(z);
            cst[y].pb(z);
        }

        int ekpranto, oporpranto;

        init();
        ekpranto = BFS(0);
        init();
        oporpranto = BFS(ekpranto);
        BFS1(oporpranto);

        printf("Case %lld:\n", ++cs);

        REP(i,n)  printf("%d\n", max(d[i],d1[i]));

        REP(i,sz) adj[i].clear(), cst[i].clear();
    }
    return 0;
}