CCF GESP 2025年3月认证 C++ 8级
题目描述
C 城可以视为由 $n$ 个结点与 $m$ 条边组成的无向图。 这些结点依次以 $1, 2, \ldots, n$ 标号，边依次以 $1 \leq i \leq m$ 连接边号为 $u_i$ 与 $v_i$ 的结点，长度为 $l_i$ 米。
小 A 的学校坐落在 C 城的编号为 $s$ 的结点。小 A 的同学们共有 $q$ 位，他们想在保证不迟到的前提下，每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校，于是找到了聪明的小 A。第 $i$ 位同学 ($1 \leq i \leq q$) 告诉小 A，他的家位置于编号为 $h_i$ 的结点，并且他每秒钟能行走 1 米。请你帮小 A 计算，每位同学从家出发需要多少秒才能到达学校呢？
输入格式
第一行，四个正整数 $n, m, s, q$，分别表示 C 城的结点数与边数，学校所在的结点编号，以及小 A 同学们的数量。
接下来 $m$ 行，每行三个正整数 $u_i, v_i, l_i$，表示 C 城中的一条无向边。
接下来 $q$ 行，每行一个正整数 $h_i$，表示一位同学的情况。
输出格式
共 $q$ 行，对于每位同学，输出一个整数，表示从家出发到学校的最短时间。
样例说明
样例 1
5 5 3 3
1 2 3
2 3 2
3 4 1
4 5 3
1 4 2
5
1
44
3
1数据范围
对于 $20\%$ 的测试点，保证 $q = 1$。
对于另外 $20\%$ 的测试点，保证 $1 \leq n \leq 500$，$1 \leq m \leq 500$。
对于所有测试点，保证 $1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 2 \times 10^5$，$1 \leq q \leq 2 \times 10^5$，$1 \leq u_i, v_i, s, h_i \leq n$，$1 \leq l_i \leq 10^6$。保证给定的图联通。
题目描述
小杨有一棵包含 $ n $ 个节点的树，其中节点的编号从 $ 1 $ 到 $ n $。
小杨设置了 $ a $ 个好点对 $\{< u_1, v_1 >, < u_2, v_2 >, \dots, < u_a, v_a >\}$ 和 $1$ 个坏点对 $< b_u, b_v >$。一个节点能被删除，当且仅当：
- 删除该节点后对于所有的 $i ( 1 \leq i \leq a )$，好点对 $ u_i $ 和 $ v_i $ 仍然连通；
- 删除该节点后坏点对 $ b_u $ 和 $ b_v $ 不连通。
如果点对中的任意一个节点被删除，其视为不连通。
小杨想知道，还有多少个节点能被删除。
输入格式
第一行包含两个非负整数 $ n $, $ a $，含义如下题面所示。
接下来 $n - 1$ 行，每行包含两个正整数 $ x_i, y_i $，代表存在一条连接节点 $ x_i $ 和 $ y_i $ 的边；
之后 $ a $ 行，每行包含两个正整数 $ u_i, v_i $，代表一个好点对 $ < u_i, v_i > $；
最后一行包含两个正整数 $ b_u, b_v $，代表坏点对 $ < b_u, b_v > $。
输出格式
输出一个非负整数，代表删除的节点个数。
样例说明
样例 1
6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 62数据范围
对于全部数据，保证有 $ 1 \leq n \leq 10^6 $, $ 0 \leq a \leq 10^5 $, $ u_i \neq v_i $, $ b_u \neq b_v $。