https://ac.nowcoder.com/acm/problem/22598
题意：有一棵树，选一个点作为根节点，要删除一些边，使得叶子节点到不了根节点，求删除的边的权值和最小。
思路：只要使叶子节点到不了根，在叶子节点那里剪掉或者在中间某一段剪掉都行，在中间某一段剪掉能够一次把下面所有的子节点剪掉。
比较花费的代价取最小值，树形dp，又是dfs，dp[u]表示剪掉以u为根节点的子树 的所有叶子节点的最小值。
父节点为u，子节点为v，dp[u]+=min(dp[v],dis[u][v]);
叶子节点设值巨大，在遍历遇到叶子的时候，必剪，形成一个dp值往上回溯。
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #define ll long long #define inf 0x3f3f3f3f using namespace std; struct Edge { int to;//指向的点 ll val;//边的权值 int next;//用于指示该点的下一条边的在edge中的位置 }; Edge edge[200005]; int head[200005]; int deg[100005]; ll dp[100005]; int n,m,s,cnt=0; void add(int u,int v,ll val) { edge[cnt].to=v; edge[cnt].val=val; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u,int last) { if(deg[u]==1 && u!=s) { dp[u]=1e18;///叶子节点的dp值设巨大 return; } for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(last!=v) { dfs(v,u); dp[u]+=min(dp[v],edge[i].val); } } } int main() { memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n-1;i++) { int u,v; ll x; scanf("%d%d%lld",&u,&v,&x); add(u,v,x); add(v,u,x); deg[u]++; deg[v]++; } dfs(s,-1); printf("%lld ",dp[s]); return 0; }