LightOJ 1094 - Farthest Nodes in a Tree（树的直径）

http://acm.hust.edu.cn/vjudge/contest/121398#problem/H

不是特别理解，今天第一次碰到这种问题。给个链接看大神的解释吧

http://www.cnblogs.com/qq2424260747/p/4740347.html

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cmath>

#include<vector>

#include<queue>

#include<algorithm>

using namespace std;

typedef long long LL;

const int maxn=;

const int INF=0x3f3f3f3f;

const int mod=;

int head[maxn], dist[maxn];

int maxs, k, Index;

struct node

{

    int u, v, next, s;

}edge[maxn<<];

void Add(int u, int v, int s)

{

    edge[k].u = u;

    edge[k].v = v;

    edge[k].s = s;

    edge[k].next = head[u];

    head[u] = k ++;

}

void DFS(int u, int s)

{

    dist[u] = s;

    if(dist[u]>maxs)

    {

        maxs = dist[u];

        Index = u;

    }

    for(int i=head[u]; i!=-; i=edge[i].next)

    {

        int v = edge[i].v;

        if(dist[v] == -)

            DFS(v, edge[i].s+dist[u]);

    }

}

int main()

{

    int T, n, u, v, s, cnt=;

    scanf("%d", &T);

    while(T --)

    {

        scanf("%d", &n);

        memset(head, -, sizeof(head));

        k = ;

        for(int i=; i<n; i++)

        {

            scanf("%d %d %d", &u, &v, &s);

            Add(u, v, s);

            Add(v, u, s);

        }

         maxs = ;

        memset(dist, -, sizeof(dist));

        DFS(, );

        memset(dist, -, sizeof(dist));

        DFS(Index, );

         printf("Case %d: %d\n", cnt++, maxs);

    }

    return ;

}