水图（牛客练习赛（DFS搜索））

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <cstring>
 7 #define INF 0x3f3f3f3f
 8 
 9 using namespace std;
10 typedef long long ll;
11 const int maxn = 50010*2;
12 int head[maxn],nxt[maxn],cost[maxn],u[maxn];
13 int cnt = 0;
14 ll sum = 0,ans = 0;
15 void Add_edge(int _u,int _v,int _c){
16     u[cnt] = _u; cost[cnt] = _c; nxt[cnt] = head[_v]; head[_v] = cnt++;
17 }
18 
19 ll read(){//这种输入处理要比scanf/printf要快一些
20     ll x = 0,f = 1;
21     char ch = getchar();
22     if(!isdigit(ch)){
23         if(ch == ‘-‘){
24             f = -1;
25             ch = getchar();
26         }
27     }
28     while(isdigit(ch)){
29         x = x*10 + ch - ‘0‘;
30         ch = getchar();
31     }
32     return x*f;
33 }
34 
35 void dfs(int now, ll res, int fa){
36     ans = max(ans, res);
37     for(int i = head[now]; ~i; i = nxt[i]){
38         if(u[i]!=fa){
39             dfs(u[i], res+(ll)cost[i], now);
40         }
41     }
42     return;
43 }
44 
45 int main(){
46     memset(head,-1,sizeof head);
47     int n = read(),x = read();
48 //    int n,x;
49 //    scanf("%d%d",&n,&x);
50     for(int i = 0; i<n-1; i++){
51         int u,v,w;
52         u = read();v = read();w = read();
53         //scanf("%d%d%d",&u,&v,&w);
54         Add_edge(u,v,w);
55         Add_edge(v,u,w);
56         sum += w;
57     }
58 
59     dfs(x, 0, 0);
60     printf("%lld\n",sum*2-ans);
61     return 0;
62 }