求树中每个点离它最远点的距离

HDU 2196

1. 树形dp

   f[u][0]:有向图dfs通过回溯(距离由子节点更新得到)求出距离每个点最远的距离,并且标记到最远点路径中经过的第一个子节点
   f[u][1]:dfs回溯时更新第二远的距离
   f[u][2]:再一次dfs根据标记 求出点u上半部分距离点u最远的距离

• 点v离它最远的点可能在2个部分,该节点的子树部分,或者是整棵树除去子树的部分,用邻接表存 有向图来做
• 由于 距离 点v的父节点 最远的点可能在 点v的子树中,那么求不出v点上半部分中距离v点最远的点,此时来维护距离 点v 第二远的点,使得该点来自点v的上半部分
• v的父节点u: 开一个数组标记每个点到距离最远点的路径中经过的第一个子节点 来 判断是否 输入 v子树部分

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;
const int maxn = 1e4+5;

struct edge{
    int to,next,w;
    edge() = default;
    edge(int a,int b,int c):to(a),next(b),w(c) {}
}e[maxn];

int cnt,head[maxn];

void add(int u,int v,int w) {
    e[++cnt] = edge(v,head[u],w);
    head[u] = cnt;
}

int n,f[maxn][3],node[maxn];

void init() {
    cnt = 0;
    memset(head,0,sizeof head);
    memset(f,0,sizeof f);
    memset(node,0,sizeof node);
}

void dfs(int u) {
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        int w = e[i].w;
        dfs(v);
        if (f[u][0] <= f[v][0] + w) {
            f[u][1] = f[u][0];
            f[u][0] = f[v][0] + w;
            node[u] = v;
        } else if (f[u][1] < f[v][0] + w)
            f[u][1] = f[v][0] + w;
    }
}

void Dfs(int u) {
    for (int i=head[u]; i; i=e[i].next) {
        int v = e[i].to;
        int w = e[i].w;
        if (node[u] == v)
            f[v][2] = max(f[u][2],f[u][1]) + w;
        else
            f[v][2] = max(f[u][2],f[u][0]) + w;
        Dfs(v);
    }
}

int main() {
//    freopen("a.txt","r",stdin);
    while (scanf("%d",&n) != EOF) {
        init();
        for (int i=2; i<=n; i++) {
            int u,w;
            scanf("%d%d",&u,&w);
            add(u,i,w);
        }
        dfs(1);
        Dfs(1);
        for (int i=1; i<=n; i++)
            printf("%d\n",max(f[i][0],f[i][2]));
    }
    return 0;
}

树的直径: dfs 2次找到树的直径的端点,在此过程中维护 每个点的到离它最远点的距离

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <string.h>

using namespace std;
const int maxn = 1e4+5;
vector<itn> p [maxn],val[maxn];
int dp[maxn],max_len,s;
void dfs(int x,int f,int len) {
	if (max_len <= len) {
		s = x;
		max_len = len;
	}
	for (int i=0; i<p[x].size(); i++) {
		int to = p[x][i];
		if (to == f) continue;
		dfs(to,x,len+val[x][i]);
		dp[to] = max(dp[to], len+val[x][i]);
	}
}
int main() {
	int n;
	while (scanf("%d",&n) != EOF) {
		int a,b;
		for (int i=2; i<=n; i++) {
			scanf("%d%d",&a,&b);
			p[i].push_back(a);
			val[i].push_back(b);
			p[a].push_back(i);
			val[a].push_back(b);
		}
		s = 0;
		max_len = 0;
		dfs(1,-1,0);
		dfs(s,-1,0);
		dfs(s,-1,0);
		for (int i=1; i<=n; i++)
			printf("%d\n",dp[i]);
		memset(dp,0,sizeof dp);
		for (int i=1; i<=n; i++) {
			p[i].clear();
			val[i].clear();
		}
	}
	return 0;
}