【Luogu3931】SAC E#1 - 一道難題 Tree

problem

solution

codes

//樹形DP
//f[u]:割掉u和u子樹中所有的葉子節點所需要的最小代價
#include<iostream>
#include<vector>using namespace std;
typedef long long LL;
const int N = (int)1e5+10, inf = 1e9;int n, S;struct node{LL to, v;node(LL to, LL v):to(to),v(v){};
};
vector<node>G[N];LL f[N];
void dp(int u, int from){if(G[u].size()==1 && u!=S)f[u] = inf;for(int i = 0; i < G[u].size(); i++){LL v = G[u][i].to, t = G[u][i].v;if(v == from)continue; //BUG1因為雙連通所以就要改參數，不能跟父節點一樣，不然會死循環dp(v,u);f[u] += min(t, f[v]);}
}int main(){cin>>n>>S;for(int i = 1; i <= n-1; i++){int a, b, c;  cin>>a>>b>>c;G[a].push_back(node(b,c));//BUG1：因為a與b誰是祖先不知道，所以要雙連通G[b].push_back(node(a,c));}dp(S,-1);cout<<f[S]<<"\n";return 0;
}