树形DP
f [i］表示 i 的子树更新上来的最大值
f [i] = max ( f [i] , f [v] + w )
ans += f [i] - f [v] - w
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 5e5 + 100 ;
struct Edge{int v , w ;Edge ( int x=0 , int y=0 ) : v(x) , w(y) {}
};
vector <Edge> edges ;
vector <int> G [N] ;void addeage ( int u , int v , int w ) {edges.push_back ( Edge ( v , w ) ) ;int tot = edges.size () ;G [u].push_back ( tot-1 ) ;
}int f [N] , vis [N] ;void dfs ( int u ) {vis [u] = 1 ;for ( int i = 0 ; i < G [u].size () ; ++ i ) {Edge e = edges [ G [u] [i] ] ;if ( vis [e.v] ) continue ;dfs ( e.v ) ;f [u] = max ( f [u] , f [e.v] + e.w ) ; }
}
LL ans = 0 ;
void dfa ( int u ) {vis [u] = 1 ;for ( int i = 0 ; i < G [u].size () ; ++ i ) {Edge e = edges [ G [u] [i] ] ;if ( vis [e.v] ) continue ;dfa ( e.v ) ;ans += f [u] - ( f [e.v] + e.w ) ;}
}int main () {int n , root ;scanf ( "%d%d" , &n , &root ) ;for ( int i = 1 ; i < n ; ++ i ) {int x , y , z ;scanf ( "%d%d%d" , &x , &y , &z ) ;addeage ( x , y , z ) ;addeage ( y , x , z ) ; }dfs ( root ); memset ( vis , 0 , sizeof vis ) ;dfa ( root );printf ( "%lld" , ans );return 0 ;
}