HDU2196Computer--二次扫描与换根

题目链接

https://cn.vjudge.net/problem/HDU-2196

给定一棵树,求离每个节点最远的点的距离是多少

分析

前置技能: 二次扫描与换根

不清楚的可以看一看之前POJ3585的博客或是自行了解

首先考虑先$O(N)$钦定点以之为根树形DP怎么做

太容易了,$f[now]$表示以$now$为根的子树中距$now$最远的距离

$f[now]=max(f[now],f[son]+dis(now,son))$

行吧,那又用二次扫描与换根做呢

我们发现$son$这个节点的答案要么是$f[now]$,要么就是往上向父亲那边走走到的最远距离

于是我们就想办法把这个向上能走的最远距离$q[now]$搞出来

$q[son]=max(q[now],f[now])+dis(now,son)$

很好理解吧,因为$now$如果为根最长路要么从上面走要么是子树中的

等等,不对啊,如果这个$f[now]$它恰好就是从$f[son]$转移过来的呢,那么不就GG了吗

于是我们再记录一个$now$为根子树中距$now$次远的距离,也就是距离次大值$g[now]$

如果$f[now]$由$f[son]$转移过来,那么

$q[son]=max(q[now],g[now])+dis(now,son)$

最后每个点的答案就是$max(f[now],q[now])$

注意得到次大值时要注意,判完小于最大值后判断是否能更新次大值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#define ll long long 
#define ri register int 
using std::min;
using std::max;
using std::swap;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=10005;
const int inf=0x7fffffff;
struct Edge{
    int ne,to,dis;
}edge[maxn<<1];
int h[maxn],num_edge=0;
inline void add_edge(int f,int to,int c){
    edge[++num_edge].ne=h[f];
    edge[num_edge].to=to;
    edge[num_edge].dis=c;
    h[f]=num_edge;
}
int n,m;
int f[maxn],g[maxn],t[maxn];//f--最大值 g--次大值,都是向下走到的最远距离
void dfs_1(int now,int fa){
    int v,x;
    int p=0,pp=0;//p--max pp--smaller than max
    for(ri i=h[now];i;i=edge[i].ne){
        v=edge[i].to;
        if(v==fa)continue;
        dfs_1(v,now);
        x=f[v]+edge[i].dis;
        if(p<x) pp=p,p=x,t[now]=v;
        else if(pp<x) pp=x;//这一句话千万不要忘了加
    }
    f[now]=p,g[now]=pp;
    return ;
}
int q[maxn];   //向上走到的最远距离
void dfs_2(int now,int fa){
    int v,x;
    for(ri i=h[now];i;i=edge[i].ne){
        v=edge[i].to;
        if(v==fa)continue;
        if(v==t[now])x=g[now];
        else x=f[now];
        q[v]=max(q[now],x)+edge[i].dis;
        dfs_2(v,now);
    }
    return ;
}
int main(){
	int x,y,z;
    while(scanf("%d",&n)!=EOF){
        memset(h,0,sizeof(int)*(n+1));
        for(ri i=2;i<=n;i++){
            read(x),read(y);
            add_edge(i,x,y);
            add_edge(x,i,y);
        }
        f[1]=g[1]=0;
        dfs_1(1,0);
        q[1]=0;
        dfs_2(1,0);
        for(ri i=1;i<=n;i++)printf("%d\n",max(f[i],q[i]));
    }
    return 0;
}