题目详情题解（0）讨论（0）提交记录（0）

CF516D.Drazil and Morning Exercise

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Drazil 和 Varda 是一对蚯蚓夫妻。他们想要找一个合适的地方抚养孩子。他们发现了一块有天然洞穴的好土壤。这个洞中有许多房间，部分房间之间通过小隧道连接，这样蚯蚓就能在它们之间移动。

我们可以把房间和小隧道看作图中的点和边。这个图是一棵树。换句话说，任意两点之间都有且只有一条唯一的路径。

每一个在图中是叶子的房间通过一条竖直的隧道与地面相连。这里的“叶子”指的是在图中只有一条出边的点。

每个房间都只能容纳一只蚯蚓居住。蚯蚓不能住在隧道里。

Drazil 和 Varda 有个计划要教育他们的孩子。他们希望所有的孩子起床后立刻做晨操！

早上来临时，所有的蚯蚓孩子会同时起床，然后每个人都会选择距离地面最远的路径下去，与其他小伙伴汇合（这些小孩都很懒，所以他们都想尽量晚点开始运动）。

Drazil 和 Varda 希望，第一个到达地面的孩子与最后一个到达地面的孩子之间的到达时间差不超过 ll（否则孩子们会分散在地面上，很难一起做运动）。

此外，被孩子们占据的房间应当形成一个连通块。换句话说，对于任意两间有孩子居住的房间，所有在它们之间路径上的房间也必须有孩子住。

问：在满足上述所有条件的前提下，Drazil 和 Varda 最多可以有多少个孩子？对于不同的 ll，Drazil 和 Varda都想知道答案。

（Drazil 和 Varda 不和孩子们住在洞穴里）

输入格式

第一行包含一个整数 nn，表示洞中共有多少间房间（2≤n≤1052 \le n \le 10^{5}）。

接下来有 n−1n-1 行，每行包含三个整数 x,y,vx, y, v（1≤x,y≤n1 \le x,y \le n，1≤v≤1061 \le v \le 10^{6}），表示房间 xx 与房间 yy 之间有一条需要花费 vv 单位时间通过的小隧道。

假设每个叶子房间通向地面的竖直隧道所需的时间都是相同的。

下一行包含一个整数 qq（1≤q≤501 \le q \le 50），表示需要处理的不同 ll 的数量。

最后一行包含 qq 个数字，每个数字表示一个 ll 的值（1≤l≤10111 \le l \le 10^{11}）。

输出格式

输出 qq 行。每行一个整数，表示对应 ll 情况下的答案。

输入输出样例

  • 输入#1

    5
1 2 3
2 3 4
4 5 3
3 4 2
5
1 2 3 4 5

    输出#1

    1
3
3
3
5

  • 输入#2

    12
5 9 3
2 1 7
11 7 2
6 5 5
2 5 3
6 7 2
1 4 4
8 5 7
1 3 8
11 12 3
10 8 2
10
13 14 14 13 13 4 6 7 2 1

    输出#2

    10
10
10
10
10
3
3
5
2
1

说明/提示

对于第一个样例，洞穴的结构如下图所示。房间 11 和 55 是叶子，所以它们都通过一条竖直隧道与地面相连。从房间 11 到 55 各自距离地面的最远路径长度分别为 12,9,7,9,1212, 9, 7, 9, 12。

如果 l=1l = 1，我们只能选择任意一间房间。

如果 l=2∼4l = 2\sim 4，我们可以选择房间 2,3,42, 3, 4 作为答案。

如果 l=5l = 5，我们可以选择所有房间。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页