You are given an undirected tree (i.e., a connected graph with no cycles), where each edge (i.e., branch) has a nonnegative weight (i.e., thickness). One vertex of the tree has been designated the root of the tree.The remaining vertices of the tree each have
unique paths to the root; non-root vertices which are not the successors of any other vertex on a path to the root are known as leaves.Determine the minimum weight set of edges that must be removed so that none of the leaves in the original tree are connected
by some path to the root.
The next n-1 lines each contain three integers ui vi wi (where ui, vi ∈ {1,……, n} and 0 <= wi <= 1000) indicating that vertex ui is connected to vertex vi by an undirected
edge with weight wi. The input file will not contain duplicate edges. The end-of-file is denoted by a single line containing "0 0".
15 15 1 2 1 2 3 2 2 5 3 5 6 7 4 6 5 6 7 4 5 15 6 15 10 11 10 13 5 13 14 4 12 13 3 9 10 8 8 9 2 9 11 3 0 0
16
//
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=3000;
struct Node
{
int t,w;
int next;
};
int V;
int root;
Node G[maxn];
int p[maxn];
int l;
void init()
{
memset(p,-1,sizeof(p));
l=0;
}
void addedge(int u,int t,int w)
{
G[l].t=t;
G[l].w=w;
G[l].next=p[u];
p[u]=l++;
}
int du[maxn];
int dfs(int u,int fath)
{
if(du[u]==1&&u!=root)
{
return (1<<29);
}
int ans=0;
for(int i=p[u];i!=-1;i=G[i].next)
{
int t=G[i].t,w=G[i].w;
if(t==fath) continue;
ans+=min(w,dfs(t,u));
}
return ans;
}
int main()
{
while(scanf("%d%d",&V,&root)==2&&V)
{
init();
memset(du,0,sizeof(du));
for(int i=0;i<V-1;i++)
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
du[u]++,du[v]++;
}
int ans=dfs(root,-1);
printf("%d\n",ans);
}
return 0;
}