学步园

描述：无根树题目，实际上就是找一条关键路也就是最长路，用dp做
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef struct
{
    int x,y;
} Pair;
vector <Pair> v[10010];
int dp[10010],sum;
bool vis[10010];
void dfs(int cur)
{
    int sec=0;
    vis[cur]=1;
    int len=v[cur].size();
    dp[cur]=0;
    for(int i=0; i<len; ++i)
    {
        int b=v[cur][i].x,c=v[cur][i].y;
        if(!vis[b])
        {
            dfs(b);
            if(dp[cur]<dp[b]+c)
            {
                sec=dp[cur];
                dp[cur]=dp[b]+c;
            }
            else if(sec<dp[b]+c) sec=dp[b]+c;
        }
    }
    if(sum<dp[cur]+sec) sum=dp[cur]+sec;
}
int main()
{
    int flag=0,count=0;
    //freopen("a.txt","r",stdin);
    while(!count)
    {
        char s[1010];
        flag=sum=0;
        for(int i=0; i<=10000; ++i) v[i].clear();
        while(1)
        {
            if(!gets(s))
            {
                count=1;
                break;
            }
            if(!flag&&s[0]==0)
            {
                if(!gets(s)) count=1;
                break;
            }
            if(flag&&s[0]==0) break;
            flag=1;
            int a,b,c;
            sscanf(s,"%d%d%d",&a,&b,&c);
            Pair p;
            p.x=b,p.y=c;
            v[a].push_back(p);
            p.x=a;
            v[b].push_back(p);
            vis[a]=vis[b]=0;
        }
        dfs(1);
        printf("%d\n",sum);
    }
    return 0;
}