大厂真题

美团研发岗 2026-09-08

本场考试概述

考试时间：2026-9-8 考试岗位：研发岗 难度评级：中等

考点分析：

• 第一题：前缀和 + 贡献法 计数（难度中等）

建议策略：

• 先把「删点后数连通块」翻译成「点数减边数」，剩下的就是一遍前缀和
• 每条边只统计在编号较小的那一端，避免重复扣除

运行说明：使用 Python 3 缓冲输入。没有官方时限与评测环境，不作语言通过率承诺。

第 1 题：站点下线演练

题目描述

美团在某座城市部署了 个配送站点，编号为 到 。站点之间铺设了 条双向专线，任意两个站点都可以经由专线互相到达，也就是说整张网络恰好构成一棵树。

小明 要对这批站点做一次逐个下线的迁移演练：从编号 的站点开始，按编号从小到大的顺序，依次把每个站点下线。某个站点一旦下线，与它直接相连的所有专线同时失效，之后不会再被启用。

演练过程中，小明 关心剩余站点被切分成了多少个互不连通的区域。两个仍在运行的站点属于同一个区域，当且仅当它们之间存在一条通路，且这条通路经过的站点全都仍在运行。孤立的单个站点也算作一个区域。

请你输出每一次下线之后，剩余站点构成的区域数量。

输入描述

第一行输入一个整数 ，表示配送站点的数量。

接下来 行，每行输入两个整数 ，表示编号 与编号 的站点之间存在一条双向专线。保证给出的专线构成一棵树。

输出描述

输出一行 个整数，相邻两个整数之间用一个空格隔开。其中第 个整数表示编号 的站点下线之后，剩余站点构成的区域数量。

样例1

输入

5
1 2
1 3
3 4
3 5

输出

2 1 2 1 0

样例解释

下线站点 后，剩余站点为 ，其中 仍由专线连成一片，站点 变成孤立站点，共 个区域。

下线站点 后，剩余站点为 ，仍连成一片，共 个区域。

下线站点 后，剩余站点为 ，它们原本都只与站点 相连，此时各自孤立，共 个区域。

下线站点 后，只剩站点 ，共 个区域。

下线站点 后，没有站点剩下，区域数量为 。

样例2

输入

4
1 2
1 3
1 4

输出

3 2 1 0

样例解释

站点 是这棵树的中心，与 都直接相连。下线站点 后，剩下的三个站点两两之间都失去了通路，各自成为一个区域，答案为 。此后每下线一个站点，区域数量就减少 ，依次得到 。

题解：贡献法 + 前缀和

思路分析

一棵 个节点的树，按编号 到 依次删点，每删完一个就要报出剩余节点分成了多少个连通块。

这是一道把”数连通块”换成”数点和边”的计数题：删点本身很难维护，难点在于找到一个扫一遍就能算出来的等价量。

算法实现

最直白的写法是每删一个点就重新跑一遍 BFS 数连通块，单次 ，总共 。 到 时是 量级的运算，必然超时。

删点只会去掉点和边、不会新增，所以任何时刻剩余部分都无环，是一片森林。森林里每个连通块都是一棵树，点数恰好比边数多 ， 个连通块合起来即

删完编号 到 的点后，剩余点数 一眼可得，只剩边数要算。

一条边 在两个端点里编号较小的那个被删时失效，此后不会被重复扣除。令 表示 的邻居中编号大于 的个数，也就是以 为较小端点的边数，就有

两式合并，答案化成一个只含前缀和的闭式：

算法实现上分三步：

第一步，读入每条边时把 加一，全程不必建邻接表 。

第二步，令 从 扫到 ，边扫边把 累进变量 ， 即上式的前缀和。

第三步，每步直接输出 。

末尾不需要特判： 时式子给出 ； 时没有任何边，同样输出 。

复杂度分析

时间复杂度：。读入 条边一次、前缀和扫描一次，瓶颈在读入；每条边至少要被看一次才知道它挂在谁身上，这个量级已经到底。

**空间复杂度 **： 。只存 数组与答案序列，省掉邻接表。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    cnt = [0] * (n + 1)
    for _ in range(n - 1):
        u, v = map(int, input().split())
        cnt[min(u, v)] += 1
    acc = 0
    ans = []
    for i in range(1, n + 1):
        acc += cnt[i]
        ans.append(str(1 - i + acc))
    print(' '.join(ans))

solve()

正确性说明

删点后的每个分量都是树，分别满足点数减边数等于一。每条边仅在较小端点删除时计数一次，因此前缀和恰好统计全部失效边，代入森林恒等式得到每一步答案。

易错点与边界

不能把失效边在两个端点各扣一次；n=1 和删完最后一个点均输出 0。Python 采用缓冲输入，但缺少官方时限与判题环境，不能承诺某种语言的通过率。

小结

优先从题面约束提炼模型，再用样例检查边界。本文保留题面数学符号的原始 SVG，代码统一为 Python 3；未给出的评测限制或规则不补作事实。