solution
因为m=n,所以题目要求也就是要求断掉一些边,使得根与叶子节点不连通,用f[i]表示以i已经无法到达它子树中的所有叶子节点的最小花费。
转移的时候分两种情况,如果断开当前点与父亲相连的边,那么其子树中的边可以都不断开,花费为0.
如果不断开当前点与父亲相连的边,那么答案就是其儿子的f值之和。
树形dp即可。
code
/* * @Author: wxyww * @Date: 2020-04-02 20:47:38 * @Last Modified time: 2020-04-02 22:53:06 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 100010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt,w; }e[N << 1]; int head[N],ejs; void add(int u,int v,int w) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w; } ll f[N]; void dfs(int u,int fa) { ll sum = 0; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(v == fa) continue; f[v] = e[i].w; // printf("%d\n",e[i].w); dfs(v,u); sum += f[v]; } if(sum) f[u] = min(f[u],sum); } int main() { memset(f,0x3f,sizeof(f)); int n = read(),m = read(),S = read(); for(int i = 1;i < n;++i) { int u = read(),v = read(),w = read(); add(u,v,w);add(v,u,w); } dfs(S,0); cout<<f[S]; return 0; }