hdu 2196 Computer (树的直径||树形dp)
题意：给出一棵树。。。求距离每个点的最远距离是多少。。。
思路：最远距离什么的。。能想到树的直径。。。但是有什么关系呢？ 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。？
1A.
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月12日 星期二 13时29分49秒
4File Name :code/hdu/2196.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E4+7;
32int n,m;
33vector < pi >edge[N];
34int d[N];
35int ans[N];
36bool vis[N];
37int beg,lst;
38int far;
39void bfs( int s)
40{
41 ms(d,0x3f);
42 ms(vis,false);
43 queue<int>q;
44 q.push(s);
45 vis[s] = true;
46 d[s] = 0 ;
47 while (!q.empty())
48 {
49 int u = q.front(); q.pop();
50 int siz = edge[u].size();
51 for ( int i = 0 ; i < siz; i++)
52 {
53 int v = edge[u][i].fst;
54 if (vis[v]) continue;
55 vis[v] = true;
56 d[v] = d[u] + edge[u][i].sec;
57 q.push(v);
58 }
59 }
60}
61int main()
62{
63 #ifndef ONLINE_JUDGE
64 freopen("code/in.txt","r",stdin);
65 #endif
66 while (~scanf("%d",&n))
67 {
68 ms(ans,0);
69 for ( int i = 1 ; i <= n ; i++) edge[i].clear();
70 for ( int i = 2 ; i <= n ; i++)
71 {
72 int u,v,w;
73 u = i;
74 scanf("%d %d",&v,&w);
75 edge[v].push_back(make_pair(u,w));
76 edge[u].push_back(make_pair(v,w));
77 }
78 bfs(1);
79 int mx = 0;
80 for ( int i = 1 ; i <= n ; i++)
81 {
82 if (d[i] > mx)
83 {
84 mx = d[i];
85 lst = i ;
86 }
87 }
88 // cout<<"lst:"<<lst<<endl;
89 far = 0 ;
90 bfs(lst);
91 for ( int i = 1 ; i <= n ; i++)
92 {
93 if (d[i]>far)
94 {
95 far = d[i];
96 beg = i ;
97 }
98 }
99 // cout<<"far:"<<far<<endl;
100 // cout<<"beg:"<<beg<<endl;
101 bfs(beg);
102 for ( int i = 1 ; i <= n ; i++)
103 ans[i] = max(ans[i],d[i]);
104 bfs(lst);
105 for ( int i = 1 ; i <= n ;i++)
106 ans[i] = max(ans[i],d[i]);
107 for ( int i = 1 ; i <= n ; i++)
108 cout<<ans[i]<<endl;
109 }
110 #ifndef ONLINE_JUDGE
111 fclose(stdin);
112 #endif
113 return 0;
114}
**20161201upd:**更新一个dp的做法（虽然用树的直径搞貌似要更好想也更直观，不过为了体会dp的思想嘛。。。）
这道题要求的是**从树上一点出发的最长路。**考虑有根树，不难想到，从树上一点u出发的最长路必然是下述两种情况之一：
（1）第一步向下走，（一直向下，走到某叶子节点）
（2）第一步向上走。
考虑树形DP：
dp[0][u] : 从节点u向下走的最长路径
dp[1][u] : 从节点u向下走的次长路径
这里，次长路径的含义是：与某条选定的最长路径不重合的路径中最长的路径。
dp[2][u] : 从节点u第一步向上走所能获得的最长路径
注意：
考虑如何转移
对于节点u，考虑u的所有子节点v，用dp[0][v]来更新dp[0][u], dp[1][u]。
至于dp[2][u], 仍考虑两种情况：
（1）第二步向下走, 这样便转移到u的父亲节点f第一步向下走的情况。
这时还要考虑用dp[0][f]还是dp[1][f]来更新dp[2][u]:（kk:因为如果第一步向上走，然后又从父亲节点回到当前节点，那么这是无意义，并且等于没有更新向上走的情况，这也是要求次小的原因）如果从f第一步走到u能走出一条从f向下的最长路，就用dp[1][f]来更新dp[2][u]，否则用dp[0][f]。
（2）第二步仍向上走，这样便转移到f第一步向上走的情况，即dp[2][f]。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年12月01日 星期四 09时03分08秒
4File Name :code/hdu/r2196.cpp
5 ************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E4+7;
32int n;
33vector < pi > edge[N];
34int dp[3][N];
35//dp[0][i]:从节点i出发第一步向下走能达到的最远距离。
36//,dp[1][i]：从节点i出发第一步向下走，能达到的次远距离（要求与最远距离的路径不相交）
37//dp[2][i]:从节点i出发第一步向上走，能达到的最远距离。
38void dfs( int u,int pre)
39{
40 for ( auto x : edge[u])
41 {
42 int v = x.fst;
43 int w = x.sec;
44 if (v==pre) continue;
45 dfs(v,u);
46 if (w+dp[0][v]>dp[0][u])
47 {
48 dp[1][u] = dp[0][u];
49 dp[0][u] = w + dp[0][v];
50 }else if (w + dp[0][v]>dp[1][u])
51 dp[1][u] = w + dp[0][v];
52 }
53}
54void dfs2( int u,int pre)
55{
56 for ( auto x : edge[u])
57 {
58 int v = x.fst;
59 int w = x.sec;
60 if (v == pre) continue;
61 if (w + dp[0][v]==dp[0][u])
62 dp[2][v] = max(dp[2][v],dp[1][u] + w);
63 else dp[2][v] = max(dp[2][v],dp[0][u] + w);
64 dp[2][v] = max(dp[2][v],dp[2][u] + w);
65 dfs2(v,u); //调用成了dfs，调试了半天。。。智力－２
66 }
67}
68int main()
69{
70#ifndef ONLINE_JUDGE
71 freopen("code/in.txt","r",stdin);
72#endif
73 while (~scanf("%d",&n))
74 {
75 ms(dp,0);
76 for ( int i = 1 ; i<= n ; i++) edge[i].clear();
77 for ( int i = 2 ;i <= n ; i++)
78 {
79 int u,v,w;
80 u = i ;
81 scanf("%d %d",&v,&w);
82 edge[u].push_back(MP(v,w));
83 edge[v].push_back(MP(u,w));
84 }
85 dfs(1,-1);
86 dfs2(1,-1);
87 for ( int i = 1 ; i <= n ; i++) printf("%d\n",max(dp[0][i],dp[2][i]));
88 }
89#ifndef ONLINE_JUDGE
90 fclose(stdin);
91#endif
92 return 0;
93}