[HOJ] 334 - 樹之國 II

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
struct P{
    int v,c;
};
int cmp(int a,int b){
    return a>b;
}
vector<P> s[100005];
int visit[100005]={0},is[100005]={0},L=0,P1,anss=-1,r=-1;
void dfs(int v,int add){
    if(add>L) L=add,P1=v;
    int i,ans=0,k;
    for(i=0;i<s[v].size();i++){
        if(visit[s[v][i].v]==0){
            visit[s[v][i].v]=1;
            dfs(s[v][i].v,add+s[v][i].c);
        }
    }
    return;
}
int dfs_r(int v,int add){
    if(add==L) return is[v]=1;
    int i,ans=0,k,flag=0;
    for(i=0;i<s[v].size();i++){
        if(visit[s[v][i].v]==0){
            visit[s[v][i].v]=1;
            flag|=dfs_r(s[v][i].v,add+s[v][i].c);
        }
    }
    return is[v]=flag;
}
void dfs2(int v,int add){
    if(is[v] && (abs(L-2*add)<anss || anss==-1)) anss=abs(L-2*add),r=v;
    int i,ans=0,k;
    for(i=0;i<s[v].size();i++){
        if(visit[s[v][i].v]==0){
            visit[s[v][i].v]=1;
            dfs2(s[v][i].v,add+s[v][i].c);
        }
    }
    return;
}
int main(){
    int m,k,i,j,x,y,z;
    scanf("%d",&m);
    for(i=0;i<m-1;i++){
        scanf("%d%d%d",&x,&y,&z);
        s[x].push_back((P){y,z});
        s[y].push_back((P){x,z});
    }
    visit[1]=1;
    dfs(1,0);
    memset(visit,0,sizeof(visit));
    visit[P1]=1;
    dfs(P1,0);
    memset(visit,0,sizeof(visit));
    visit[P1]=1;
    dfs_r(P1,0);
    memset(visit,0,sizeof(visit));
    visit[P1]=1;
    dfs2(P1,0);
    printf("%d\n",r);
}