#P14974. [2026年省选联测]亦可赛艇
[2026年省选联测]亦可赛艇
亦可赛艇(excite)
题目描述
下山市的水网系统由 个节点和 条河道组成,赛艇可以在河道任意方向行驶,保证水网构成一棵树。
赛艇竞赛委员会能够建设两种不同类型的节点,一种是始终节点,选手们可以将这个点作为赛艇路线的起点或终点;另一种是补给节点,选手们可以在这个节点进行补给和休息,但不能作为自己路线的起点或终点。
显然,一个补给节点是有效的,当且仅当存在一个航线,从一个始终节点出发,到达另一个始终节点,且这条航线经过这个补给节点;一个建设方案是经济的,当且仅当它建设的每一个补给节点都是有效的。特别地,一个节点可以同时被建设为始终节点和补给节点,此时,它也是有效的。
如下图,左边两个都是经济的,但最右边的不是经济的。其中,红点代表始终节点,蓝点代表补给节点。

现在,赛艇竞赛委员会设计了一个长度为 的建设计划序列,第 个建设计划为将编号为 的节点建设为类型为 的节点,对一个节点的多次建设均可生效。现在竞赛委员会想知道,对于每一个 ,如果从第 个建设计划开始最多可以连续建设多少个计划,使得全部建设完以后,建设方案是经济的。
输入格式
第一行一个整数 ,表示水网中的节点数量。
接下来的 行,每行两个整数 ,表示 和 之间有河道相连。
接下来一行一个整数 ,表示计划序列的长度。
接下来的 行,第 行一个字符 和一个整数 ,表示将编号为 的节点建设为类型为 的节点,其中 s 表示始终节点,b 表示补给节点。
输出格式
输出 行,每行一个整数 ,表示从第 个建设计划开始最多可以连续建设多少个计划,使得全部建设完以后建设方案是经济的,即最大的 ,使得完成区间 的所有建设计划后,建设方案是经济的。
样例 1
输入
6
2 1
1 3
3 5
5 6
4 3
8
b 1
s 2
b 6
s 3
b 4
s 5
b 3
s 4
输出
0
1
0
5
4
3
0
1
样例 2
输入
7
4 2
2 1
1 3
3 6
5 2
3 7
6
s 4
b 5
b 6
s 7
b 2
s 3
输出
1
0
0
1
0
1
样例 3
输入
2
1 2
5
s 1
b 1
s 1
b 1
s 1
输出
5
4
3
2
1
样例 3 说明
从任意位置开始,都可以执行到计划序列末尾;若执行了补给节点建设,1 号节点也同时是始终节点,因此补给节点有效。答案依次为 5、4、3、2、1。
数据范围
,;所有节点编号在 到 之间。保证输入河道构成树,每个计划的类型为 s 或 b。
同一节点可以出现任意多次任意类型的建设计划。只检查整个选定区间全部完成后的建设方案;不要求该区间的每个中间前缀都经济。
本版保留现行 Hydro 评分:全部测试点统一共 100 分。
原题来源:ICPC 2025 LAC — Exciting Business Opportunities(洛谷 P15099)。本地原题解明确注明这一来源;据其完整输入说明补齐归档缺失的范围。