思路：

　　树形DP求直径；

　　答案是边权总和*2-直径；

　　dp[i][1]::以i为根的子树中最长的路径；

　　dp[i][0]::以i为根的子树中次长的路径；

 

来，上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define maxn 100005int n,s,E[maxn<<1],V[maxn<<1],W[maxn<<1],cnt;int head[maxn],dp[maxn][2],sum,ans=0;inline void in(int &now){    char Cget=getchar();now=0;    while(Cget>'9'||Cget<'0') Cget=getchar();    while(Cget>='0'&&Cget<='9')    {        now=now*10+Cget-'0';        Cget=getchar();    }}void dfs(int now,int fa){    bool res=true;    int pos=0,gs=0;    for(int i=head[now];i;i=E[i])    {        if(V[i]==fa) continue;        res=false,dfs(V[i],now);        if(W[i]+dp[V[i]][0]>gs) gs=W[i]+dp[V[i]][0],pos=V[i];    }    if(res) return ;    dp[now][0]=gs,gs=0;    for(int i=head[now];i;i=E[i])    {        if(V[i]==fa||V[i]==pos) continue;        if(W[i]+dp[V[i]][0]>gs) gs=W[i]+dp[V[i]][0];    }    dp[now][1]=gs,ans=max(ans,dp[now][1]+dp[now][0]);}int main(){    in(n),in(s);int u,v,w;    for(int i=1;i