旅行计划

Description

某个国家有$N$个城市，编号$0$至$N - 1$，他们之间用$N - 1$条道路连接，道路是双向行驶的，沿着道路你可以到达任何一个城市。你有一个旅行计划，这个计划是从编号$K$的城市出发，每天到达一个你没有去过的城市，并且旅途中经过的没有去过的城市尽可能的多（如果有$2$条路线，经过的没有去过的城市同样多，优先考虑编号最小的城市），直到所有城市都观光过一遍。现在给出城市之间的交通图$T$，以及出发地点$K$，你来设计一个旅行计划，满足上面的条件。例如：
($K = 2$)

第$1$天 从$2$到$0$ (城市$1$和$0$变成去过的)
第$2$天 从$0$到$6$ (城市$4$和$6$变成去过的)
第$3$天 从$6$到$3$ (城市$3$变成去过的)
第$4$天 从$3$到$5$ (城市$5$变成去过的)
上图的输入数据为：$0 1 2 2 1 4$。共$7$个节点，除节点$0$之外，共$6$行数据。
第$1$个数$0$表示$1$到$0$有$1$条道路。
第$2$个数$1$表示$2$到$1$有$1$条道路。

Input

第$1$行：$2$个数$N$，$K$($1 \le N \le 50000, 0 \le K \le N - 1$)
第$2 - N + 1$行：每行一个数，表示节点之间的道路。

Output

输出旅行的路线图，即每天到达的城市编号。

Input示例

7 2
0
1
2
2
1
4

Output示例

2
0
6
3
5

Solution

以下搬自51nod题解。考虑将树根设为K，观察到以下结论：

1. 每次必然会走到叶子，否则可以继续向下走到叶子，使得访问的点增多。
2. 考虑每次访问到的未访问的点，一定是与叶子相连的、在叶子到点K路径上的一条连续的链，所以问题可以转化为：令每个叶子分别支配一条链，使得标号小的点尽量支配多的点，最后根据支配的点数多少、标号大小依次访问。以做法可以是树上贪心，从深到浅依次确定每个点被其子树里哪个叶子支配，然后使得那个点的支配点个数加一，最后用基数排序排出支配点数降序、标号大小升序即可。

然而我看不懂这个题解，我的做法是这样的：先$DFS$一遍，算出以每棵子树最深的深度，然后维护一个根连接的子树的优先队列，每次取出一棵深度最大的子树，走到这棵子树的最深的节点，这里的根并不只是$k$，而是已经被访问过的点。每次选择一个点后，把这条路径上新产生的子树加入优先队列中。时间复杂度$O(nlog_2{n})$。

Standard

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define fi first
#define se second
#define mp make_pair

typedef pair<int, int> PII;

const int N = 50010;

int n, k;

int tot = -1, head[N];
struct Edge {
    int p, next;
} edge[N << 1];
inline void Add(int u, int v) {
    edge[++tot] = (Edge) {v, head[u]};
    head[u] = tot;
    return;
}

int fa[N];
PII md[N];

void DFS(int u) {
    md[u] = mp(1, -u);
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].p;
        if (v == fa[u]) continue;
        fa[v] = u;
        DFS(v);
        PII cur = md[v];
        ++cur.fi;
        if (md[u] < cur) md[u] = cur;
    }
    return;
}

priority_queue<PII> pq;
bool exist[N];

void Update(int u) {
    for (; ~u && !exist[u]; u = fa[u]) {
        exist[u] = 1;
        for (int i = head[u]; ~i; i = edge[i].next) {
            int v = edge[i].p;
            if (v == fa[u]) continue;
            if (!exist[v]) pq.push(md[v]);
        }
    }
    return;
}

int main() {
    scanf("%d%d", &n, &k);
    memset(head, -1, sizeof(head));
    for (int u = 1; u < n; ++u) {
        int v;
        scanf("%d", &v);
        Add(u, v);
        Add(v, u);
    }
    fa[k] = -1;
    DFS(k);
    for (int i = head[k]; ~i; i = edge[i].next) {
        int v = edge[i].p;
        pq.push(md[v]);
    }
    exist[k] = 1;
    printf("%d\n", k);
    while (!pq.empty()) {
        PII cur = pq.top();
        pq.pop();
        int u = -cur.se;
        Update(u);
        printf("%d\n", u);
    }
    return 0;
}