题目内容
输入描述
输出描述
样例
输入
7
1 2
1 3
2 4
2 5
4 6
4 7
输出
2
题目解析
代码实现
C++
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
// 全局变量
int n;
vector<vector<int>> adj;
vector<int> depth;
vector<vector<int>> children;
int maxDepth;
// 计算每个节点深度并构建子树
void dfsDepth(int u, int p) {
for (int v : adj[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
maxDepth = max(maxDepth, depth[v]);
children[u].push_back(v);
dfsDepth(v, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
adj.assign(n+1, {});
for (int i = 0; i < n-1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
depth.assign(n+1, 0);
children.assign(n+1, {});
maxDepth = 0;
dfsDepth(1, 0);
// dp[v][h]: 子树 v 在目标叶深度 h 时最大保留节点数
// 为节省空间，用滚动数组：prev[h], cur[h]
vector<int> best(n+1, -INF), nxt;
int answer = 0;
// 对每个候选深度 h 从 0 到 maxDepth
for (int h = 0; h <= maxDepth; h++) {
// 自底向上后序遍历：我们可以用一次栈模拟，也可按节点编号逆序（因为深度越大后序肯定处理先）
// 这里简单地按深度从大到小分层遍历
vector<vector<int>> byDepth(maxDepth+1);
for (int v = 1; v <= n; v++) {
byDepth[depth[v]].push_back(v);
}
best.assign(n+1, -INF);
// 从最大深度层到 0 层
for (int d = maxDepth; d >= 0; d--) {
for (int v : byDepth[d]) {
if (depth[v] > h) {
best[v] = -INF;
} else if (depth[v] == h) {
// 变为叶子
best[v] = 1;
} else {
int sum = 0;
for (int u : children[v]) {
if (best[u] > 0) sum += best[u];
}
if (sum > 0) best[v] = sum + 1;
else best[v] = -INF;
}
}
}
answer = max(answer, best[1]);
}
// 最少移除数 = 总数 - 最大保留数
cout << (n - answer) << "\n";
return 0;
}
Python
import sys
sys.setrecursionlimit(10000)
n = int(sys.stdin.readline())
adj = [[] for _ in range(n+1)]
for _ in range(n-1):
u, v = map(int, sys.stdin.readline().split())
adj[u].append(v)
adj[v].append(u)
depth = [0]*(n+1)
children = [[] for _ in range(n+1)]
max_depth = 0
def dfs(u, p):
global max_depth
for v in adj[u]:
if v == p: continue
depth[v] = depth[u] + 1
max_depth = max(max_depth, depth[v])
children[u].append(v)
dfs(v, u)
dfs(1, 0)
# dp[v][h] 用滚动数组 best[v] 存储当前 h 的值
answer = 0
for h in range(max_depth+1):
# 按深度分层
by_depth = [[] for _ in range(max_depth+1)]
for v in range(1, n+1):
by_depth[depth[v]].append(v)
best = [-10**9]*(n+1)
for d in range(max_depth, -1, -1):
for v in by_depth[d]:
if depth[v] > h:
best[v] = -10**9
elif depth[v] == h:
best[v] = 1
else:
s = sum(best[u] for u in children[v] if best[u] > 0)
best[v] = s + 1 if s > 0 else -10**9
answer = max(answer, best[1])
print(n - answer)
Java
import java.io.*;
import java.util.*;
public class Main {
static int n;
static List<List<Integer>> adj;
static int[] depth;
static List<List<Integer>> children;
static int maxDepth = 0;
static void dfs(int u, int p) {
for (int v : adj.get(u)) {
if (v == p) continue;
depth[v] = depth[u] + 1;
maxDepth = Math.max(maxDepth, depth[v]);
children.get(u).add(v);
dfs(v, u);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int i = 0; i < n-1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
adj.get(u).add(v);
adj.get(v).add(u);
}
depth = new int[n+1];
children = new ArrayList<>();
for (int i = 0; i <= n; i++) children.add(new ArrayList<>());
dfs(1, 0);
int answer = 0;
for (int h = 0; h <= maxDepth; h++) {
List<List<Integer>> byDepth = new ArrayList<>();
for (int i = 0; i <= maxDepth; i++) byDepth.add(new ArrayList<>());
for (int v = 1; v <= n; v++) {
byDepth.get(depth[v]).add(v);
}
int[] best = new int[n+1];
Arrays.fill(best, Integer.MIN_VALUE / 2);
for (int d = maxDepth; d >= 0; d--) {
for (int v : byDepth.get(d)) {
if (depth[v] > h) {
best[v] = Integer.MIN_VALUE / 2;
} else if (depth[v] == h) {
best[v] = 1;
} else {
int sum = 0;
for (int u : children.get(v)) {
if (best[u] > 0) sum += best[u];
}
best[v] = (sum > 0 ? sum + 1 : Integer.MIN_VALUE / 2);
}
}
}
answer = Math.max(answer, best[1]);
}
System.out.println(n - answer);
}
}