P9304 「DTOI-5」3-1题解，c++树的遍历例题

题意

给定以 n ( 1 ≤ n ≤ 1 0 5 ) n(1 \leq n \leq 10^5) n(1≤n≤105) 个节点的树，根节点为 1 1 1。对于每个节点共有一下两种边与其相连：

• 1 ≤ i , j ≤ n 1 \leq i,j \leq n 1≤i,j≤n，代表花费 1 1 1 个费用从 i i i 走到 j j j,无使用次数限制，共 n − 1 n - 1 n−1 条。
• 2 ≤ i ≤ n 2 \leq i \leq n 2≤i≤n，代表花费 0 0 0 个费用从 i i i 走到 1 1 1，只能用不超过 1 1 1 次。

要求输出访问 1 − n 1-n 1−n 个节点最少需要花费多少费用。

思路

考虑 n n n 个节点的费用，即这道题：

首先，如果我们每个点都必须遍历一遍，再返回 1 1 1，那么总费用必定是 2 × ( n − 1 ) 2 \times (n - 1) 2×(n−1)，因为每条边都必须走两遍。

对于传送操作，和 CF61D 类似，只需要删除一个最长边，就可以让操作数最小，总花费为 2 × ( n − 1 ) − d e e p e s t 2 \times (n - 1) - deepest 2×(n−1)−deepest， d e e p e s t deepest deepest 表示最长边长度。

从 n n n 反向考虑删点，第 i i i 个节点花费为 2 × ( i − 1 ) − d e e p e s t 2 \times (i - 1) - deepest 2×(i−1)−deepest， d e e p e s t deepest deepest 表示当前最长边长度。如果还有不在最长链上的点可以删除，则 a n s i = a n s i + 1 − 2 ans_i = ans_{i + 1} - 2 ansi​=ansi+1​−2，否则因为每次 d e e p e s t ← d e e p e s t − 1 deepest \gets deepest - 1 deepest←deepest−1，因此 a n s i = a n s i + 1 − 1 ans_i = ans_{i + 1} - 1 ansi​=ansi+1​−1，如果用从 1 1 1 正推的话，公式如下：

a n s i = { a n s i − 1 + 1 x ≤ d e e p e s t + 1 a n s i − 1 + 2 d e e p e s t ≤ x ≤ n ans_i = \begin{cases} ans_{i -1} + 1 & x \leq deepest + 1 \\ ans_{i - 1} + 2 & deepest \leq x \leq n \end{cases} ansi​={ansi−1​+1ansi−1​+2​x≤deepest+1deepest≤x≤n​

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n; 
int head[100005],nex[200005],to[200005],cnt = 0,a[200005];
void add(int x,int y) {
	nex[++cnt] = head[x];
	head[x] = cnt;
	to[cnt] = y;
}
int deep[100005],ans = -1e18;
void find_deep(int now,int fa) {
	for(int i = head[now];i;i = nex[i]) {
		if(to[i] != fa) {
			deep[to[i]] = deep[now] + 1;
			find_deep(to[i],now);
		} 
	}
	return;
}
signed main() {
	scanf("%lld",&n);
	for(int i = 1;i < n;i++) {
		int x,y;
		scanf("%lld %lld",&x,&y);
		add(x,y),add(y,x);
	}
	find_deep(1,1);
	for(int i = 1;i <= n;i++) ans = max(ans,deep[i]);
	for(int i = 1;i <= ans;i++) a[i] = a[i - 1] + 1;
	for(int i = ans + 1;i < n;i++) a[i] = a[i - 1] + 2;
	for(int i = 0;i < n;i++) printf("%lld\n",a[i]);
    return 0;
}