#P14974. [2026年省选联测]亦可赛艇

    ID: 14190 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>图论排序与序列处理倍增计算几何扫描线数据结构CF2600线段树DFS构造

[2026年省选联测]亦可赛艇

亦可赛艇(excite)

题目描述

下山市的水网系统由 nn 个节点和 n−1n-1 条河道组成,赛艇可以在河道任意方向行驶,保证水网构成一棵树。

赛艇竞赛委员会能够建设两种不同类型的节点,一种是始终节点,选手们可以将这个点作为赛艇路线的起点或终点;另一种是补给节点,选手们可以在这个节点进行补给和休息,但不能作为自己路线的起点或终点。

显然,一个补给节点是有效的,当且仅当存在一个航线,从一个始终节点出发,到达另一个始终节点,且这条航线经过这个补给节点;一个建设方案是经济的,当且仅当它建设的每一个补给节点都是有效的。特别地,一个节点可以同时被建设为始终节点和补给节点,此时,它也是有效的。

如下图,左边两个都是经济的,但最右边的不是经济的。其中,红点代表始终节点,蓝点代表补给节点。

三种建设方案示意图

现在,赛艇竞赛委员会设计了一个长度为 mm 的建设计划序列,第 ii 个建设计划为将编号为 aia_i 的节点建设为类型为 bib_i 的节点,对一个节点的多次建设均可生效。现在竞赛委员会想知道,对于每一个 1≤i≤m1\le i\le m,如果从第 ii 个建设计划开始最多可以连续建设多少个计划,使得全部建设完以后,建设方案是经济的。

输入格式

第一行一个整数 nn,表示水网中的节点数量。

接下来的 n−1n-1 行,每行两个整数 u,vu,v,表示 uu 和 vv 之间有河道相连。

接下来一行一个整数 mm,表示计划序列的长度。

接下来的 mm 行,第 n+1+in+1+i 行一个字符 bib_i 和一个整数 aia_i,表示将编号为 aia_i 的节点建设为类型为 bib_i 的节点,其中 s 表示始终节点,b 表示补给节点。

输出格式

输出 mm 行,每行一个整数 ansians_i,表示从第 ii 个建设计划开始最多可以连续建设多少个计划,使得全部建设完以后建设方案是经济的,即最大的 jj,使得完成区间 [i,i+j−1][i,i+j-1] 的所有建设计划后,建设方案是经济的。

样例 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。

数据范围

2≤n≤1052\le n\le10^5,1≤m≤1051\le m\le10^5;所有节点编号在 11 到 nn 之间。保证输入河道构成树,每个计划的类型为 s 或 b。

同一节点可以出现任意多次任意类型的建设计划。只检查整个选定区间全部完成后的建设方案;不要求该区间的每个中间前缀都经济。

本版保留现行 Hydro 评分:全部测试点统一共 100 分。

原题来源:ICPC 2025 LAC — Exciting Business Opportunities(洛谷 P15099)。本地原题解明确注明这一来源;据其完整输入说明补齐归档缺失的范围。