题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2196
题目意思：
给你一个无向图，但是没有环，因为有N个点，只有N-1条边
要你求出N个点在这个图上能够走的最远距离
解题思路：
这是赤裸裸的无环的无向图，我们可以把它转化为一棵树
其实以任意一个节点作为树根都是可以的，做N遍DFS就可以
但是会超时，所以我们要想办法解决超时的问题，也就是减少DFS的次数
我们可以先做一遍DFS，求出每个节点到自己子树上的最远距离，这个可以通过类似回溯的方法，但是我们保存在数组中了
然后再第二次DFS的时候，我们根据之前的DFS可以求出每个节点的父节点不经过自己的最远距离
然后将这些一起比较就可以求出来每个节点所能走的最远距离
下面上代码：
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- #include<vector>
- using namespace std;
- struct node
- {
- int v;
- int len;
- };
- const int maxn = 10005;
- const int inf = 0x3f3f3f3f;
- int dp[maxn];
- int n;
- vector<node> computer[maxn];
- void read_init()
- {
- for(int i=0;i<=n;i++)
- computer[i].clear();
- for(int i=1;i<=n;i++)
- dp[i] = 0;
- int a,b;
- node tmp;
- for(int i=2;i<=n;i++)
- {
- scanf("%d%d",&a,&b);
- tmp.v=a;
- tmp.len=b;
- computer[i].push_back(tmp);
- tmp.v=i;
- tmp.len=b;
- computer[a].push_back(tmp);
- }
- }
- void dfs_to_son(int root,int fa)
- {
- for(int i=0;i<computer[root].size();i++)
- {
- int v = computer[root][i].v;
- if(v==fa)
- continue;
- dfs_to_son(v,root);
- dp[root] = max(dp[root],computer[root][i].len+dp[v]);
- computer[root][i].len = computer[root][i].len+dp[v];
- }
- }
- void dfs_find_longest_path(int root,int fa)
- {
- int not_son_longest=0;
- for(int i=0;i<computer[fa].size();i++)
- {
- int v = computer[fa][i].v;
- if(v==root)
- continue;
- not_son_longest = max(not_son_longest,computer[fa][i].len);
- }
- for(int i=0;i<computer[root].size();i++)
- {
- int v = computer[root][i].v;
- if(v==fa)
- {
- computer[root][i].len = not_son_longest+computer[root][i].len;
- break;
- }
- }
- for(int i=0;i<computer[root].size();i++)
- {
- dp[root] = max(dp[root],computer[root][i].len);
- }
- for(int i=0;i<computer[root].size();i++)
- {
- int v = computer[root][i].v;
- if(v==fa)
- continue;
- dfs_find_longest_path(v,root);
- }
- }
- int main()
- {
- while(~scanf("%d",&n))
- {
- read_init();
- dfs_to_son(1,0);
- dfs_find_longest_path(1,0);
- for(int i=1;i<=n;i++)
- printf("%d\n",dp[i]);
- }
- return 0;
- }