自动搬运

查看原文

来自洛谷，原作者为

	yszkddzyh 回首向来萧瑟处，归去，也无风雨也无晴

搬运于2025-08-24 22:52:36，当前版本为作者最后更新于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;
}