有一棵由N个结点构成的树，每一条边上都有其对应的权值。现在给定起点，求从该点出发的一条路径（至少有一条边）使得这条路径上的权值之和最大，并输出这个最大值。
Input第一行一个正整数T，代表数据组数。每组数据第一行两个正整数n(2<=n<=10^5),s(1<=s<=n)，分别表示树结点数目以及给定的起点，点的编号从1至N。接下来M行，每行三个整数x,y,z,(1<=x,y<=n,|z|<=1000)，代表编号为x和y的点之间有一条权值为z的双向边。
Output每组数据输出一行，即所找到路径的最大权值(格式参见样例)。
Sample Input 2 3 1 1 2 10 1 3 5 5 5 1 5 70 4 3 100 5 3 -10 2 5 60 Sample Output Case #1: 10 Case #2: 90 虽然知道这道题要用dfs，但无论是在构造节点时，还是具体实现dfs时独有一种无从下手的无力感，果然 还是数据结构接触的太少了，完全没建立想关的意识。虽然自己知道大致的思路。#include<iostream>#include<vector>#include<cstdio>#include<cstring>using namespace std;struct Edge{int v,w;};const int maxn=111111;int flag[maxn];//标记已经访问过的点int sum[maxn];//存储权的和vector<Edge>it[maxn];//原本it就是一个无限制的一维数组，但将it定义为it[maxn]后就变成了二维数组；这样void dfs(int t){ flag[t]=1; int itm=it[t].size();//得到与点t临街的所有点，这也是vector的好处； for(int i=0;i<itm;i++)//遍历t所有的临街点，并不断dfs，知道没临街点为止； { int h=it[t][i].v; if(flag[h]==0) { sum[h]=sum[t]+it[t][i].w; dfs(h); } }}int main(){ //freopen("1.txt","r",stdin); int T,co=0;cin>>T; while(T--) { int n,s;cin>>n>>s;memset(flag,0,sizeof(flag));memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++)it[i].clear();//这里必须clear; for(int i=0;i<n-1;i++) { int x,y,z;cin>>x>>y>>z; Edge pre; pre.w=z; pre.v=x; it[y].push_back(pre);//为甚是it[y]而不是it[x]是有讲究的，这样在访问点x时，it[x]里存储的是点x的邻接点和相关联边，这是非常重要的； pre.v=y; it[x].push_back(pre); } dfs(s);int ans=0; for(int i=1;i<=n;i++) { ans=max(ans,sum[i]); } printf("Case #%d: %d\n",++co,ans); } return 0;} 这道题无论在邻接点的表现形式上（利用vector，这样就可以将与点x邻接的所有点y1,y2,y3之流尽数存储在it[x]中，非常形象的体现了邻接的意义），还是dfs的具体实现上都事非常经典的，值得学习；