P9872 DFS Order 题解

yszkddzyh · 2023-11-25 19:30:59 · 题解

因为是从根节点开始按任意顺序进行深度优先遍历，所以如果想让一个节点尽可能早地遍历到，那显然就应该先朝它这个方向遍历，但由于是深度优先，所以它能遍历到的最早的序号应该就是它的深度，因为你必须经过它的祖先结点才能到它。

反之，如果想让它尽可能晚地遍历到，那就需要先去把别的点尽量都遍历一遍，但同样地，由于是深度优先，所以你不能把这个节点的子节点先遍历了再遍历这个节点，由此，答案即为所有节点数减这个节点的子树的大小加一。

这样，我们 dfs 预处理出每个节点的深度和子树大小，问题迎刃而解。

注意，代码中存储节点深度和子树大小的两个数组在多测中不需要清空，如果你用 memset 会超时第 3 个点（深受其害）。

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector <int> G[N];
int t, n, siz[N], dep[N];

void dfs(int u, int f){
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v == f) continue;
        dfs(v, u), siz[u] += siz[v];
    }
    return;
}

int main(){

    ios :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n;
//      memset(dep, 0, sizeof(dep));
//      memset(siz, 0, sizeof(siz));
        for(int i = 1; i <= n; i++) G[i].clear();
        for(int i = 1, u, v; i < n; i++){
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1, 0);
        for(int i = 1; i <= n; i++)
            cout << dep[i] << ' ' << n - siz[i] + 1 << '\n';
    }

    return 0;
}