当前位置：首页 > ds >正文

在线机考|2025年华为暑期实习春招秋招编程题（最新）——第2题_网络整改

ds 2025/7/13 10:08:29

题目内容

输入描述

输出描述

样例

输入

输出

题目解析

代码实现

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 到 maxDepthfor (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 = 0def dfs(u, p):global max_depthfor v in adj[u]:if v == p: continuedepth[v] = depth[u] + 1max_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**9elif depth[v] == h:best[v] = 1else:s = sum(best[u] for u in children[v] if best[u] > 0)best[v] = s + 1 if s > 0 else -10**9answer = 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);}
}

查看全文

http://www.xdnf.cn/news/13900.html