# Farthest Nodes in a Tree

Given a tree (a connected graph with no cycles), you have to find the farthest nodes in the tree. The edges of the tree are weighted and undirected. That means you have to find two nodes in the tree whose distance is maximum amongst all nodes.

Input starts with an integer T (≤ 10), denoting the number of test cases. Each case starts with an integer n (2 ≤ n ≤ 30000) denoting the total number of nodes in the tree. The nodes are numbered from 0 to n-1. Each of the next n-1 lines will contain three integers u v w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 10000) denoting that node u and v are connected by an edge whose weight is w. You can assume that the input will form a valid tree.

Output

For each case, print the case number and the maximum distance.

Sample Input

```    2
4
0 1 20
1 2 30
2 3 50
5
0 2 20
2 1 10
0 3 29
0 4 50```

Sample Output

```    Case 1: 100
Case 2: 80```

```#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int> pa;

bool flag[100100];
int step[100100];
vector<pa>v[100100];
int a,b,c,sum;
int t,n;

int dfs(int x)
{
sum=0;
memset(flag,0,sizeof flag);
memset(step,0,sizeof step);
queue<int>q;
q.push(x);
flag[x]=1;
int yy=0;
while(!q.empty() )
{
int xx=q.front() ;
q.pop() ;
if(step[xx]>sum)
{
sum=step[xx];
yy=xx;
}
pa p;
for(int i=0;i<v[xx].size() ;i++)
{
p=v[xx][i];
int y=p.first ;
if(!flag[y])
{
flag[y]=1;
step[y]=step[xx]+p.second;
q.push(y);
}
}
}
return yy;
}
int main()
{
ios::sync_with_stdio(false);
cin>>t;

for(int i=1;i<=t;i++)
{
cin>>n;
for(int k=0;k<n;k++)
v[k].clear() ;
for(int j=1;j<n;j++)
{
cin>>a>>b>>c;
v[a].push_back(make_pair(b,c));//双向存储便于查找
v[b].push_back(make_pair(a,c));
}
dfs(dfs(0));
cout<<"Case "<<i<<": "<<sum<<endl;
}

return 0;
}```

# E-Computer

```#include<iostream>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

typedef pair<int,int> pa;
int n,maxlen,s;
vector<pa>v[100100];
int dp[100100];

int dfs(int x,int y,int l)
{
if(maxlen<=l)
{
maxlen=l;
s=x;
}
pa p;
for(int i=0;i<v[x].size() ;i++)
{
p=v[x][i];
if(p.first ==y) continue;
else
{
dfs(p.first ,x,l+p.second);
dp[p.first]=max(dp[p.first],l+p.second);
}
}
}

int main()
{
while(cin>>n)
{
int x,y;
memset(dp,0,sizeof dp);
for(int i=0;i<=n;i++) v[i].clear() ;
for(int  i=2;i<=n;i++)
{
cin>>x>>y;
v[x].push_back(make_pair(i,y));
v[i].push_back(make_pair(x,y));
}
s=0;
maxlen=0;
maxlen=0;
dfs(1,-1,0);
dfs(s,-1,0);
dfs(s,-1,0);
for(int i=1;i<=n;i++) cout<<dp[i]<<endl;
}
return 0;
} ```

0 条评论

• ### HDU-1811-Rank of Tetris

#HDU-1811-Rank of Tetris HDU-1811-Rank of Tetris

• ### 背包九讲

01背包九讲里面最简单的一种了，但是也是最重要的一种，其他的几种基本上都可以用01背包的解题思路来去解决，接下来结合例题来解决一下吧；

• ### D. Minimax Problem

time limit per test:5 seconds memory limit per test:512 megabytes inputstandard ...

• ### Java工具集-支持各种类型快速排序工具

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### UVA 10600 ACM Contest and Blackout(次小生成树)

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=...

• ### 水果Fruit（母函数） - HDU 2152

转眼到了收获的季节，由于有TT的专业指导，Lele获得了大丰收。特别是水果，Lele一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。 ...

• ### 初级程序员面试不靠谱指南（三）

二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当，因为&这个符号在C/C++不止有一种含义，但是因为其经常会和指针一起出现在被问的问题列表上，所...

• ### 复习C艹（更新中）

之前在win7中运行c／c++下个vc就可以编译运行了，现在换了Mac，上网一看需要下个xcode，哎哟，好大啊，当时又没网，捉急，咦，mac的终端可以编译cp...

• ### POJ Test for Job(DAG上拓扑排序)

题意是给了n个点，m条边(单向边)，然后每个点都有一个点权(存在负权)，问从入度为0的点开始到出度为0的点，最大的权值和为多少。

• ### PTA 7-1 畅通工程之局部最小花费问题（35 分）

7-1 畅通工程之局部最小花费问题（35 分） 某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城...