hdu 2196 Computer (树的直径||树形dp)

hdu2196

题意:给出一棵树。。。求距离每个点的最远距离是多少。。。

思路:最远距离什么的。。能想到树的直径。。。但是有什么关系呢? 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次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,调试了半天。。。智力-2
    }
}
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;
}