Description
在山上一共有N个站点需要检查，检查员从山顶出发去各个站点进行检查，各个站点间有且仅有一条通路，检查员下山前往站点时比较轻松，而上山时却需要额外的时间，问最后检查员检查完所有站点时所需要的额外时间最少是多少。
Input
包含多组数据 每组数据输入第一行为一个整数N 表示站点个数（1<=N<=100000）,接下去N-1 行 每行3个整数 x，y，z(1<=z<=10000) 检查站x为检查站y的父节点，x,y之间有一条通路，从y到x需要额外z的时间。（父节点在子节点上方，山顶固定标号为1）
Output
输出一行一个整数表示最少需要花费的额外时间。
Sample Input
6 1 2 1 2 4 1 1 3 1 3 5 1 3 6 1
Sample Output
3
/* 简单dfs 这是一棵有根树，我们只需确定从根节点到哪个叶子节点（记为P）路程上权值和最大，计算出这个路程权值maxlen 记所有路径的权值为sum，答案就是sum-maxlen，即从root走到P之后不再登山。 */ #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; struct node { int son,len; node(int a,int b){son=a; len=b;} }; vector<node> s[100005]; int f[100005]; int n,maxlen,sum; void dfs(int root) { for(int i=0;i<s[root].size();i++) { f[s[root][i].son]=f[root]+s[root][i].len; maxlen=max(maxlen,f[s[root][i].son]); dfs(s[root][i].son); } return; } int main() { while(~scanf("%d",&n)) { memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) s[i].clear(); maxlen=0; sum=0; for(int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); sum+=z; s[x].push_back(node(y,z)); } dfs(1); //printf("%d %d ",sum,maxlen); printf("%d ",sum-maxlen); //for(int i=1;i<=n;i++) printf("%d ",f[i]); } return 0; }