bef-> NO.21

Veröffentlicht am

「一本通 5.2 练习 2」旅游规划

题目描述

W 市的交通规划出现了重大问题，市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。但由于人员不足，W 市市长决定只在最需要安排人员的路口安排人员。

具体来说，W 市的交通网络十分简单，由 n 个交叉路口和 n−1 条街道构成，交叉路口路口编号依次为 0,1,⋯ ,n−10,1,\cdots ,n-10,1,⋯,n−1 。任意一条街道连接两个交叉路口，且任意两个交叉路口间都存在一条路径互相连接。

经过长期调查，结果显示，如果一个交叉路口位于 W 市交通网最长路径上，那么这个路口必定拥挤不堪。所谓最长路径，定义为某条路径 p=(v1,v2,v3,⋯ ,vk)p=(v_1,v_2,v_3,\cdots,v_k)p=(v1,v2,v3,⋯,vk)，路径经过的路口各不相同，且城市中不存在长度大于 kkk 的路径，因此最长路径可能不唯一。因此 Ｗ 市市长想知道哪些路口位于城市交通网的最长路径上。

输入格式

第一行一个整数 n；

之后 n−1 行每行两个整数 u,v，表示 u 和 v 的路口间存在着一条街道。

输出格式

输出包括若干行，每行包括一个整数——某个位于最长路径上的路口编号。为了确保解唯一，请将所有最长路径上的路口编号按编号顺序由小到大依次输出。

样例

样例输入

1
2
3
4
5
6
7
8
9
10
10
0 1
0 2
0 4
0 6
0 7
1 3
2 5
4 8
6 9

样例输出

1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
8
9

数据范围与提示

对于全部数据，

题解

一句话题意，求一棵树上所有直径上的所有点。

我们先想想如何判断一个点是否是直径上的点。

考虑它在一棵树上延伸的最长链和次长链，假设这两个加起来等于直径，那它就是直径上的点。

假如它小于直径上，我们是否能证明他不在直径上呢？

显然反证法，假设它在一条直径上，直径两端点必定有一个是他的最长链端点，否则这就不是直径了。

假设另一个端点不是直径端点，设它次长链端点为V，显然V和最长链端点构成新的直径，与假设矛盾。

也就是说一个点在直径上，它的最长链和次长链端点就是直径两个端点。

因此我们只需要知道每个点能伸展的最长链和次长链即可。

假设我们以任意点为根，树上一个点的最长链和次长链必定是子树内最长链，子树内次长链，子树外最长链（子树外次长链无论如何能被子树内最长链代替，没有用）中的二者。

这就是一个典型的换根dp，或者说up and down

假设以s为根，先up出以s为根的有根树每个点子树内的最长链和次长链。

up完后，我们可以顺便求出直径长度（直径必定是某个点子树内的最长链和次长链之和，假如不是，那这条直径上的点就造成了矛盾）。

这时候我们假如枚举根来继续这样求，时间复杂度

超时的原因是我们没有考虑根转移后状态的联系。

1539936382998

我们以最顶端为根，已经完成了up的过程。

这时候我们想向子节点转移。

显然以子节点为根最长链和次长链只有上述说的三种情况。但是要注意这个原根的最长链可能就是由这个节点转移过来的

因此我们在up最长链的时候记录最长链由哪个子节点转移过来的。down的时候假设当前子节点是原根最长链的转移者，就用根的次长链来更新，实现常数换根转移。

总复杂度

Code:

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
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define INF 0x7fffffff
#define maxn 200005
int f[maxn] , g[maxn] , p[maxn] , q[maxn] ,  tot , cnt , head[maxn] , n , u , v , maxx , dw[maxn] , ver[maxn] , dist;
struct edge{
    int next , to , dis;
}e[maxn*2];
inline void add(int x ,int y , int d)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    e[cnt].dis = d;
    head[x] = cnt;
}
void up(int x , int fx)
{
    f[x] = 0 , g[x] = 0;
    for(int i = head[x] ; i ; i = e[i].next)
    {
        if(e[i].to == fx)   continue;
        up(e[i].to , x);
        if(f[e[i].to] + e[i].dis > f[x])
        {
            g[x] = f[x];
            f[x] = f[e[i].to] + e[i].dis;
            p[x] = e[i].to;
        }
        else if(f[e[i].to] + e[i].dis > g[x])
            g[x] = f[e[i].to] + e[i].dis;
    }
}
void down(int x , int fx , int dis)
{
    // printf("%d %d : \n",x,fx);
    if(p[fx] != x)
    {
        // printf("bef : %d %d %d\n",f[x] , g[x] , f[fx] + dis);
        if(f[fx] + dis > f[x])
        {
            g[x] = f[x];
            f[x] = f[fx] + dis;
            p[x] = fx;
        }
        else if(f[fx] + dis > g[x])
            g[x] = f[fx] + dis;
        // printf("las : %d %d %d\n",f[x] , g[x] , f[fx] + dis);
    }
    else
    {
        // printf("bef : %d %d %d\n",f[x] , g[x] , g[fx] + dis);
        if(g[fx] + dis > f[x])
        {
            g[x] = f[x];
            f[x] = g[fx] + dis;
            p[x] = fx;
        }
        else if(g[fx] + dis > g[x])
            g[x] = g[fx] + dis;
        // printf("las : %d %d %d\n",f[x] , g[x] , g[fx] + dis);
    }
    // if(f[x] + g[x] == dist) ver[++tot] = x;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            down(e[i].to , x, e[i].dis);
}
int main()
{
    scanf("%d",&n);
    int x , y , d;
    for(int i = 1 ; i <= n-1 ; ++i)
        scanf("%d%d",&x,&y) , add(x+1,y+1,1) , add(y+1,x+1,1);
    up(1,0);
    for(int i = 1 ; i <= n ; ++i)
        dist = std::max(dist , f[i] + g[i]);
    down(1,0,0);
    // std::sort(ver+1,ver+tot+1);
    // for(int i = 1 ; i <= tot ; ++i)
    //     printf("%d\n",ver[i]-1);
    for(int i = 1 ; i <= n ; ++i)
        if(f[i] + g[i] == dist)
            printf("%d\n",i-1);

}

Ps:写的时候又犯了睿智错误，把变量和数组名写错了。。。