hdu 2196 Computer (树的直径||树形dp)
题意：给出一棵树。。。求距离每个点的最远距离是多少。。。
思路：最远距离什么的。。能想到树的直径。。。但是有什么关系呢？ 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。？
1A.
/* ***********************************************
Author :111qqz
Created Time :2016年07月12日 星期二 13时29分49秒
File Name :code/hdu/2196.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E4+7;
int n,m;
vector < pi >edge[N];
int d[N];
int ans[N];
bool vis[N];
int beg,lst;
int far;
void bfs( int s)
{
ms(d,0x3f);
ms(vis,false);
queue<int>q;
q.push(s);
vis[s] = true;
d[s] = 0 ;
while (!q.empty())
{
int u = q.front(); q.pop();
int siz = edge[u].size();
for ( int i = 0 ; i < siz; i++)
{
int v = edge[u][i].fst;
if (vis[v]) continue;
vis[v] = true;
d[v] = d[u] + edge[u][i].sec;
q.push(v);
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
while (~scanf("%d",&n))
{
ms(ans,0);
for ( int i = 1 ; i <= n ; i++) edge[i].clear();
for ( int i = 2 ; i <= n ; i++)
{
int u,v,w;
u = i;
scanf("%d %d",&v,&w);
edge[v].push_back(make_pair(u,w));
edge[u].push_back(make_pair(v,w));
}
bfs(1);
int mx = 0;
for ( int i = 1 ; i <= n ; i++)
{
if (d[i] > mx)
{
mx = d[i];
lst = i ;
}
}
// cout<<"lst:"<<lst<<endl;
far = 0 ;
bfs(lst);
for ( int i = 1 ; i <= n ; i++)
{
if (d[i]>far)
{
far = d[i];
beg = i ;
}
}
// cout<<"far:"<<far<<endl;
// cout<<"beg:"<<beg<<endl;
bfs(beg);
for ( int i = 1 ; i <= n ; i++)
ans[i] = max(ans[i],d[i]);
bfs(lst);
for ( int i = 1 ; i <= n ;i++)
ans[i] = max(ans[i],d[i]);
for ( int i = 1 ; i <= n ; i++)
cout<<ans[i]<<endl;
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
**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]。
/* ***********************************************
Author :111qqz
Created Time :2016年12月01日 星期四 09时03分08秒
File Name :code/hdu/r2196.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E4+7;
int n;
vector < pi > edge[N];
int dp[3][N];
//dp[0][i]:从节点i出发第一步向下走能达到的最远距离。
//,dp[1][i]：从节点i出发第一步向下走，能达到的次远距离（要求与最远距离的路径不相交）
//dp[2][i]:从节点i出发第一步向上走，能达到的最远距离。
void dfs( int u,int pre)
{
for ( auto x : edge[u])
{
int v = x.fst;
int w = x.sec;
if (v==pre) continue;
dfs(v,u);
if (w+dp[0][v]>dp[0][u])
{
dp[1][u] = dp[0][u];
dp[0][u] = w + dp[0][v];
}else if (w + dp[0][v]>dp[1][u])
dp[1][u] = w + dp[0][v];
}
}
void dfs2( int u,int pre)
{
for ( auto x : edge[u])
{
int v = x.fst;
int w = x.sec;
if (v == pre) continue;
if (w + dp[0][v]==dp[0][u])
dp[2][v] = max(dp[2][v],dp[1][u] + w);
else dp[2][v] = max(dp[2][v],dp[0][u] + w);
dp[2][v] = max(dp[2][v],dp[2][u] + w);
dfs2(v,u); //调用成了dfs，调试了半天。。。智力－２
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
while (~scanf("%d",&n))
{
ms(dp,0);
for ( int i = 1 ; i<= n ; i++) edge[i].clear();
for ( int i = 2 ;i <= n ; i++)
{
int u,v,w;
u = i ;
scanf("%d %d",&v,&w);
edge[u].push_back(MP(v,w));
edge[v].push_back(MP(u,w));
}
dfs(1,-1);
dfs2(1,-1);
for ( int i = 1 ; i <= n ; i++) printf("%d\n",max(dp[0][i],dp[2][i]));
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}