湖南大学 2021 程序设计训练笔记

所有代码均已上传至我的 GitHub 及我的 Gitea。不保证代码均正确（如不正确会在 Commit 详情标出），正确的也不保证为最优解。

1. Dijkstra?

来源：CF20C 数据已弱化

个人难度评级：3

问题描述

给定一个含权的无向图，顶点编号为 $1-n$ ，你的任务为找出顶点 $1$ 到顶点 $n$ 之间的最短路径。

输入形式

输入的第一行为两个整数 $n$ 和 $m(2 \le n \le 10^5,0 \le m \le 10^5)$ ，其中 $n$ 为顶点数， $m$ 是边数。

接下来的 $m$ 行包含用形式 $a_i$ 、 $b_i$ 和 $w_i(1 \le a_i, b_i \le n,1 \le w_i \le 10^6)$ ，这 $a_i$ 、 $b_i$ 是边的端点，而 $w_i$ 是边的长度。

该图可能包括环，或者一对顶点之间包含多条边。

输出形式

如果无路径，输出 $-1$ ，否则输出最短路径，如果有多个，则输出字典序最小的路径。

对于两个整数序列 $A(a_1、a_2、…)$ 和 $B(b_1、b_2、…)$ ，称序列 $A$ 字典序小于序列 $B$ 当且仅当，存在 $k \ge 1$ ， $i \le k$ 时， $a_i \le b_i$ ， $i=k$ 时， $a_i < b_i$ 。

样例输入

样例输出

1 4 3 5

解题思路

首先提前说一下，别看它 $10^7$ 的数据范围，其实并没有几条边，可以说是弱中弱了。如果想通过原题，可以试着看看洛谷等地的题解。

所以说这是个模板题，就像 Luogu P3371 一样？不是，起码不完全是。

它加入了路径输出，而且还要输出字典序最小的路径。我的解决方法是为每个点增加一个 vector，存储从 1 号点到这里最短且字典序最小的路径，当检测到更短的路径时一律替换为更短的路径并更新 dist 数组，而当检测到同样长度的路径时，如果字典序更小，就替换路径。

如何比较 vector 的字典序？那当然是手撸比较函数。那 string 自带比较函数，为什么不用 string 存路径？因为它会认为 1 3 15 2 要比 1 3 5 2 字典序更小。

2. 0-1 串

来源：Codeforces 327A Flipping Game

个人难度评级：2

问题描述

对于一个包含 $n$ 个整数元素的序列 $a_1$ 、 $a_2$ 、…、 $a_n$ ，每个元素的值或者是 $0$ 或者是 $1$ ，选择两个下标 $i$ 和 $j(1 \le i \le j \le n)$ , 对于所有的此范围内的元素 $a_k(i \le k \le j)$ ，执行操作 $a_k=1-a_k$ 。

选择合适的 $i$ 和 $j$ ，执行上述操作一次之后，可以得到的新序列中包含 $1$ 的个数最多是多少？

输入形式

输入的第一行为一个整数 $n(1 \le n \le 100)$ ，接来的一行为 $n$ 个整数，每个整数或者是 $0$ 或者是 $1$ 。

输出形式

输出为一个整数，表示执行一次上述操作后可以获得的最大 $1$ 的个数。

样例输入 1

5
1 0 0 1 0

样例输出 1

样例输入 2

4
1 0 0 1

样例输出 2

样例说明

在第一个样例中，选择 $i=2, j=5$ , 改变后的序列为 $[1 1 1 0 1]$ ，包含 4 个 1，很显然无法改变为 $[1 1 1 1 1]$ 。

在第二个样例中，选择 $i=2, j=3$ ，改变后的序列为 $[1 1 1 1]$ ，包含 4 个 1。

解题思路

CG 上的题目标签中赫然写着”动态规划 “” 前缀和 “，但这毕竟是一道 CF A 题，出现了范围十分小的数据范围，O(n3) 的暴力枚举算法也能轻松通过，即使是 CF 原数据。枚举左端点和右端点，分别计算区间左边、中间和右边的和相加张，在各种情况中取最大值即可。注意左右端点可以重合，也可以延伸到尽头。

如果嫌左右加和太慢，似乎也可以写棵线段树？其实前缀和优化之后根本不需要对左右两边进行加和，只需要对翻转的部分进行操作。对此，你可以看洛谷的题解，有一些写得不错。

3. 良心树

来源：Codeforces 1143C

个人难度评级：4

问题描述

给定一颗有根树，顶点编号为 $1~n$ ，树是一个无环的连通图，有根树有一个特定的顶点，称为根。

顶点 $i$ 的祖先是从根到顶点 i 的路径上除顶点 $i$ 以外的所有顶点，顶点 $i$ 的父母是 $i$ 的祖先中最接近 $i$ 的顶点，每个顶点都是它父母的孩子。在给定的树中，顶点 $i$ 的父母是顶点 $p_i$ ，对于根， $p_i$ 为 $-1$ 。例如：

这是一个 $n=8$ 个顶点的树，根为 $5$ ，顶点 $2$ 的父母为 $3$ ，顶点 1 的父母为 $5$ , $6$ 的祖先为 $4$ 和 $5$ ， $7$ 的祖先为 $8$ 、 $3$ 和 $5$ 。

在树中，其中一些顶点不尊重其他一些顶点，实际上，如果 $c_i=1$ ，表示顶点 $i$ 不尊重它的所有祖先，而如果 $c_i=0$ ，则表示它尊重它所有的祖先。

你需要一个一个地删除一些顶点，在每一步中，选择一个非根顶点，它不尊重它的父母并且它的所有孩子顶点也不尊重它。如果有几个这样的顶点，你需要选择具有最小编号的顶点。当你删除了这样的一个顶点 $v$ , 则 $v$ 的所有子顶点与 $v$ 的父母顶点相连。

上图是删除顶点 $7$ 的示例。

直到树中无满足删除标准的顶点，则上述过程停止。按顺序输出你删除的所有顶点，注意这个顺序的唯一的。

输入形式

输入的第一行为一个整数 $n(1 \le n \le 10^5)$ ，表示树的顶点数。

接下来的 $n$ 行描述了整颗树：第 $i$ 行包含两个整数 $p_i$ 和 $c_i(1 \le p_i \le n,0 \le c_i \le 1)$ ，这里 $p_i$ 是顶点 $i$ 的父母，若 $c_i=0$ ，表示顶点 $i$ 尊重它的父母， $c_i=1$ ，表示顶点 $i$ 不尊重它的父母， $p_i=-1$ 时，表示顶点 $i$ 是树的根，同时 $c_i=0$ 。

输出形式

如果树中至少有一个顶点被删除，则按照顺序输出顶点编号，否则输入 $-1$ 。

样例输入 1

样例输出 1

1 2 4

样例输入 2

样例输出 2

-1

样例输入 3

样例输出 3

样例说明

第一个样例的删除过程如下（在图中， $c_i=1$ 的顶点是黄色的）

首先删除顶点 $1$ ，因为它不尊重祖先并且它的所有孩子也不尊重它，而 $1$ 是这样的顶点中编号最小的
删除后顶点 $2$ 将连接到顶点 $3$
然后删除顶点 $2$ ，因为它不尊重祖先并且它的所有孩子也不尊重它。
顶点 $4$ 将连接到顶点 $3$
然后删除顶点 $4$ ，因为它不尊重祖先，并且它的所有孩子也不尊重它（无孩子）
无更多顶点可删

在第二个样例中，无需删除顶点

顶点 $2$ 和 $3$ 的孩子尊重它们
顶点 $4$ 和 $5$ 尊重它们的祖先

在第三个样例中显示如下

解题思路

CG 系统上的翻译帮了倒忙，Codeforces 的题目原文也不难懂，建议去看英文原文，能够对题面有更好的理解。

下面介绍的是一种思考有难度，而其他方面十分有优势的做法。不需要图论知识，不需要树论知识（需要的知识原题已讲明），更不需要 DFS！推荐大家去看 Luogu@songhongyi 的题解，讲得非常清楚，切中要害：题解 CF1143C 【Queen】 - 一位编程爱好者 - 洛谷博客 (luogu.org)

这道题的一个条件十分重要：不尊重就是不尊重所有祖先，同样尊重的话也是尊重所有祖先。如果一个顶点被移除，那么它的所有子结点都不尊重它，它自己也不尊重父结点。这一支，以前是，把子结点连到父结点之后也是，都是不尊重父结点的。至于尊重的，根本就不会被移除，当然更没有影响。也就是说，移除顶点时，临近点的受尊重状态并不会随之改变。

这样，从小到大删除并输出符合条件的结点，就可以转化为仅从小到大输出符合条件的结点，而不用真正的删除，反正删不删造成的影响实际上并不重要；洛谷的题目翻译隐去了这部分推导过程，使得题目变得过于简单，所以我认为不甚合适。

基于以上原因，我们进一步的确定，根本不需要建树。将每个结点输入并将那两个条件计算即可。上述的那篇题解提供了非常好的办法：位运算，准确的说是位与。初始将每个结点都设为被所有子节点不尊重，然后对它每个子节点，如果有一个尊重它，按位与之后，就是 0，即被尊重。

4. 最昂贵的旅行

个人难度评级：2

问题描述

这个国家有 $n$ 个城市，编号从 $0~n-1$ ，城市网络中没有任何环路，但可以从任意一个城市出发沿公路直接或间接到达其他城市。

有人住在编号为 $0$ 的城市里，他希望去其他的一个城市旅行，但他不想付出更多的成本，所以他想知道去哪个城市的成本是最高的。

输入形式

输入的第一行为一个整数 $n(3 \le n \le 100)$ ，接下来的 $n-1$ 行每行包括 $3$ 个整数 $u、v、c(0 \le u,v \le n-1,1 \le c \le 10^4)$ ，意为在城市 $u$ 和 $v$ 之间有公路直接相连，且旅行需要花费的成本为 $c$ 。

输出形式

输出为一个整数，表示从城市 $0$ 出发去到其他的某个城市，需要付出的最大成本。

样例输入 1

样例输出 1

样例输入 2

样例输出 2

样例输入 3

样例输出 3

解题思路

题意：求单源最短路径中的最大值。

其实基本就是 dijkstra 模板题，如果你会了第 1 题，没有理由不会这道题。

一个小坑：道路是双向的，这体现在样例 2 中，如果是单向道路，那么城市 1 就不能到达，而题中保证了所有城市都可以到达。

5. 猫与餐厅的故事

来源：Codeforces 580C（数据差别很大）

个人难度评级：4

问题描述

公司今天发薪，阿迪想与朋友们去餐厅庆祝一下。

他住在一个非常神奇的公园里，这个公园是一个根在顶点 $1$ ，且由 $n$ 个顶点组成的有根树，顶点 1 也就是他的住所。然而不幸的是，公园也有许多的猫，阿迪已经找出了所有包含猫的顶点。

公园的叶子顶点都有餐厅，阿迪想选择一家他可以去的餐厅，但很不幸，他非常害怕猫，因而如果从餐厅去往他家的路径上有连续包含猫的数量超过 $m$ 时，他将不能去往这家餐厅。

你的任务是帮助他确认他能去的餐厅的数量。

输入形式

输入的第一行包含两个整数 $n$ 和 $m(2 \le n \le 10^5, 1 \le m \le n)$ ，分别表示树的顶点数以及对于阿迪来说可以忍受的最大的包含猫的连续顶点数。

第二行包含 $n$ 个整数 $a_1$ 、 $a_2$ 、…、 $a_n$ ，这里的每个 $a_i$ 或者为 $0$ （顶点 $i$ 无猫），或者为 $1$ （顶点 $i$ 有猫）。

接下来的 $n-1$ 行包含用形式 “ $x_i$ $y_i$ ”（ $1 \le x_i,y_i \le n, x_i \neq y_i$ ）表示的树的边，表示顶点 $x_i$ 和顶点 $y_i$ 之间有边相连。

输出形式

输出为一个整数，表示从阿迪家去往叶子顶点的路径上至多包含 $m$ 只猫的叶子顶点的数量。

样例输入 1

样例输出 1

样例输入 2

7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7

样例输出 2

样例说明

很显然，树是具有 $n$ 个顶点 $n-1$ 条边的连通图，有根树是有一个称为根的特殊顶点的树。

在样例一中

包含猫的顶点变为红色，餐厅在顶点 2、3、4，阿迪不能去到在顶点 2 的餐厅。

在样例二中

餐厅在顶点 4、5、6、7，阿迪不能去到 6 和 7。

解题思路

这题我 CF 全过了，但 CG 全部 WA，扫了一眼，似乎 CG 的样例比 CF 还猛（以至于无法显示整个样例）…… 翻译质量倒是还凑合，起码比英语读着舒服了。

此题的数据结构是树，但不是二叉树，所以并不建议使用二叉树的表示方式记录，而应该使用图的方式（毕竟树也是图嘛）。你可以使用邻接矩阵或者邻接表存储，但我更推荐链式前向星，下面的思路也是基于链式前向星展开的。

需要注意结点的编号从 1 开始。考虑到链式前向星，我建议边的下标也从 1 开始。为了防止输入边的方向并不是从根节点向叶子结点，可以考虑存成无向图，两种方向都存进去，不会 MLE。

在构建完成整张图之后，使用 DFS 从结点 1 开始搜索，除了要维护当前结点编号之外，还要维护当前路径已经连续有猫的数量。一旦后者大于 m，直接 return。

除此之外，我们都知道到了叶子结点就要计数。但是如何判断叶子结点呢？我们用 $head[currPos]$ 表示当前结点第一条边的终点下标，而 $next[i]==1$ 第 i 条边不再有下一条同起点边。叶子结点只连着一条边，所以需要 $next[head[currPos]]==1$ ，来表示 currPos 只连了一条边（即父节点）。同时为了防止无父节点的根节点被误判，还需要加入 $currPos!=1$ 。

访问过的结点打上 visited 标记，因存的是无向图，这样可以防止重复访问。visited 的结点也可以直接 return。

之后就是对当前结点连接的结点的遍历了，如果有猫则当前连续猫数 + 1，否则清空。

6. 旅行的期望值

来源：Codeforces 839C

个人难度评级：4

问题描述

在古代阿拉伯王国，有 $n$ 座城市有 $n-1$ 条道路，每条道路连接两座城市，人们可以从任意城市出发到达另外一座城市。

西蒙住在第一个城市，骑着马沿着马路去旅行，但是这个国家非常多雾，他也看不清楚马把他带向了哪里，当他们到达一个城市时（包括第一个城市），接下来可以去往与该城市相连的任意一个城市，然而他的马有些奇特，就是只会去往以前从未到达过的城市，且对于下一个城市的选择是等概率的，直到没有可以去往的城市为止。

设每条道路的长度为 1，从第一个城市开始旅行，那么这次旅行的期望长度（旅行距离的期望值）的多少？

如果你对期望值（平局值）的定义不太了解，可以查阅相关资料。

输入形式

输入的第一行为一个整数 $n(1 \le n \le 100000)$ ，表示城市的数量。

接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i(1 \le u_i,v_i \le n,u_i \neq v_i)$ ，表示由第 $i$ 条道路连接的城市。

输入保证能从一个城市到达其他任意一个城市。

输出形式

输出一个数，表示此次旅行的距离的期望值，旅行从城市 1 开始。

答案的绝对或相对误差不能超过 $10^{-6}$ ，也就是说，如果你的答案为 $a$ ，正确答案为 $b$ ，则如果 $\frac{|a-b|}{max(1,b)} \le 10^{-6}$ 则检查程序会认为你的答案是正确的。

样例输入 1

样例输出 1

1.500000000000000

样例输入 2

样例输出 2

2.000000000000000

样例说明

在第一个样例中，旅行可以在等概率在城市 3 或 4 结束，城市 3 的距离为 1 而城市 4 的距离为 2，因此，期望长度为 1.5.

在第二个样例中，旅行可以在城市 4 或 5 结束，两个距离都是 2，因此期望长度为 2。

解题思路

又是奇奇怪怪但不影响做题的翻译。原题还贴了 “期望” 的Wikipedia 链接（英文），CG 由于众所周知的原因已经去掉了。

这张图仍然是一棵树，和上题的遍历方法差不太多。每个结点遍历时都要传入一个 double 类型概率值，代表遍历到此点的概率。因为向子节点走是等概率的，所以子节点的概率要除子节点数量，而这个数量需要提前算。

计算期望，可以选择逐点加上遍历到此点的概率，也可以额外传一个深度的变量，遍历到叶子结点时乘上到此结点的概率一起加到期望里。

题目要求相对误差不超过 $10^{-6}$ 即可，Codeforces 确实是这么判的，它的测试数据和样例一样，留了 15 位小数；而 CG 似乎严格按照 7 位小数比对判断，所以直接输出 7 位小数就可以了。

7. 有效的 BFS

来源：Codeforces 1037D

个人难度评级：5

问题描述

在图的 BFS（广度优先搜索）中，通常采用队列来保存当前顶点的邻接点，但对对应邻接点的存入顺序没有要求，因此对于一个图的 BFS 结果可以有多个，在本问题中，从顶点 1 开始，请验证一个给定的顶点序列是否为一个有效的 BFS 序列？

输入形式

输入的第一行为一个整数 $n (1 \le n \le 2 \times 10^{5})$ ，表示树中节点的数量。

接下来 $n-1$ 行描述了树的边，每行包含两个整数 $x$ 和 $y(1 \le x,y \le n)$ ，表示对应边的两个端点，输入保证给定的图构成一颗树。

最后一行为 $n$ 个互不相同的整数 $a_{1}$ 、 $a_2$ 、……、 $a_n (1 \le a_i \le n)$ ，代表待检验的顶点序列。

输出形式

如果待检验的序列是一个正确的 BFS 序列，输出 “Yes”，否则输出 “No”。

样例输入 1

样例输出 1

Yes

样例输入 2

样例输出 2

No

解题思路

个人认为这个图用邻接链表方便点，那就不用前向星了。

BFS 中，属于同一个父节点的子节点，访问的顺序是任意的，但惟需保证先访问谁就要先访问谁的儿子。整体的思路就是模拟题中的 BFS 过程，如果发现按照题中的序列并不能完成 BFS，那么就输出 no 然后 return。

维护一个访问序列的队列 $visitSeq$ ，就是正常 DFS 模拟过程中的访问序列；以及一个待检查队列 $reqSeq$ ，来自题目要求的 BFS 队列。

可以想到，对于遍历到的每一个 BFS 结点，它的 $childNum$ 个子节点必须全部放置于 $reqSeq$ 的队首，而队首的 $n$ 个元素也必须全部是这些子节点，否则就不是一个合法的 BFS 序列（根据先访问谁就先访问谁的子节点）。具体一点，就是逐个检查队首的前 $childNum$ 个元素是否包含在当前元素子节点的集合中，如果包含，则此处的遍历顺序是合法的，将这个元素推入待访问队列；否则，它就不合法。

更具体地来讲，给访问过的结点打上一个 $visited$ 标记，以分辨父节点和子节点。遍历每个结点的时候，将所有 $visited==0$ 的结点扔进一个子节点的 set，它的大小就是 $childNum$ 。然后检查 $reqSeq$ 的前 n 个结点是否在 set 内，如果在，则将其推入 $visitSeq$ ，同时 reqSeq.pop()；否则，直接输出 no 然后 return。

对于子节点非常多的测试数据（如 Codeforces 原题数据 48），装进 set 是一个非常明智的提速方法， $O(log n)$ 查找起来嗖嗖的快。同时也要注意树的遍历第一个结点必须是 1，忽视这一点会卡在原题数据 39。

8. 数组跳远

来源：Codeforces 1472C

个人难度评级：5

问题描述

对于一个具有 $n$ 个元素的数组 $a$ , 执行以下操作：

首先，选择下标 $i(1 \le i \le n)$ —— 设置为数组的开始位置，放一个标记在 $i$ 处（在值 $a_i$ 的地方）
当 $i \le n$ 时，你的得分将增加 $a_i$ ，且将标记向右移动 $a_i$ 个位置，也就是说用 $i+a_i$ 替换 $i$ ，继续这个过程
如果 $i>n$ ，则结束操作

例如，如果 $n=5$ 且 $a=[7, 3, 1, 2, 3]$ ，则可以进行以下操作

选择 $i=1$ ，操作过程为 $i = 1 \overset{+7}{\longrightarrow} 8$ ，最后得分为 $a_1 = 7$
选择 $i = 2$ ，操作过程为 $i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8$ , 最后得分为 $a_2 + a_5 = 6$
选择 $i = 3$ ，操作过程为 $i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6$ , 最后得分为 $a_3 + a_4 = 3$
选择 $i = 4$ ，操作过程为 $i = 4 \overset{+2}{\longrightarrow} 6$ , 最后得分为 $a_4 = 2$
选择 $i = 5$ ，操作过程为 $i = 5 \overset{+3}{\longrightarrow} 8$ , 最后得分为 $a_5 = 3$

请选择合适的开始位置，使得经过上述操作后可获得最大的分数。

输入形式

输入的第一行为一个整数 $t$ ( $1 \leq t \leq 10^4$ )，表示测试用例的组数。

每个测试用例的第一行为一个整数 $n$ ( $1 \leq n \leq 2 \cdot 10^5$ )，表示数组 $a$ 的元素个数

接下来一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \leq a_i \leq 10^9$ )，表示数组 $a$ 的元素

输出形式

对于每个测试用例，输出独立一行，表示选择合适的开始位置后经过上述操作可以获得的最大分数。

样例输入

4
5
7 3 1 2 3
3
2 1 4
6
2 1000 2 3 995 1
5
1 1 1 1 1

样例输出

解题思路

借鉴自洛谷 @Melon_Musk 的题解。讲得清楚明白，我觉得我没必要再写了。

因为 $a[i]$ 是按照位置顺序输入的， $a[i]$ 数组没必要全存起来，随输入随处理即可，可以极大幅度节省内存消耗；此人写了一个快读，输入大量数据时能够节省时间消耗，但本题时间限制为 2s，scanf 实测能过，甚至 cin 应该也可以。

9. 踩点上课

来源：Codeforces 1520G

个人难度评级：5

问题描述

阿迪通常开着闹钟睡觉，这样他才不至于上课迟到。

他想知道能否赶上第一节课，为了不迟到，他需要知道从家到学校所需要的最少时间是多少。

阿迪生活的城市是一个 $n\times{m}$ 的矩形区域，其中每个单元 $(i, j)$ 由一个数字 $a_{ij}$ 来表示

数字为 $-1$ 时表示该单元被占用，禁止通行
数字为 $0$ 时表示该单元是空闲的，阿迪可以穿过
数字为 $x$ ( $1 \le x \le 10^9$ ) 时表示该单元包含入口，需要耗费的时间成本为 $x$ ，包含入口的单元也是空闲的，可以自由通行

从任何包含入口的单元出发，阿迪可以去往任何包含入口的其他单元，从入口 $(i,j)$ 到入口 $(x,y)$ 的时间成本总和为 $a_{ij} + a_{xy}$ 。

除了在两个包含入口的单元之间移动，他也可以在具有相邻边的未被占用的单元之间移动，耗费的时间为 $w$ 。实际上，他也可以进入一个包含入口的单元而不使用它。

开始时，阿迪处在左上角单元 $(1, 1)$ ，而学校位于右下角 $(n,m)$ 。

输入形式

输入的第一行包含三个整数 $n$ 、 $m$ 和 $w$ ( $2 \le n, m \le 2 \cdot 10^3$ , $1 \le w \le 10^9$ )，此处 $n$ 和 $m$ 是城市的大小， $w$ 是在未被占用的单元之间移动所需要的时间。

接下来的 $n$ 行每行包含 $m$ 个数 ( $-1 \le a_{ij} \le 10^9$ )，表示对单元的描述。

输入保证单元 $(1, 1)$ 和 $(n,m)$ 是空闲的。

输出形式

输出为一个数，表示阿迪去往学校需要花费的最少时间，如果他不能去到学校，则输出 $-1$ 。

样例输入

5 5 1
0 -1 0 1 -1
0 20 0 0 -1
-1 -1 -1 -1 -1
3 0 0 0 0
-1 0 0 0 0

样例输出

样例说明

第一组样例的说明如下：

解题思路

英语基础还可以的同学可以去看：Codeforces Round #719 (Div. 3) Editorial - Codeforces。

简单来说，首先如果用传送门，必只能用一次以达到花费最小，这样只需要考虑用传送门和不用两种情况。不用传送门，就是找起点到终点的最短路径；而如果用传送门，则需要分别找到与起点和终点间成本最小的点（不只有 $w \times {dist(D,i)}_{min}$ ，还要加上该传送门的权值 $a_i$ ，才能代表使用该传送门的成本），然后相加。将两者比较，即可得到最小成本。

具体一点来说，就是分别从起点和终点开始两次 BFS，若到达另一端则更新起点终点距离，若遇到传送门则算出成本并更新最小成本值。

注意使用 long long 存储与距离有关的变量；各种初始值也要设定大一些，否则无法通过 Codeforces 测试数据（可能会卡在 #122 左右，后面几个全是大数据）。

未曾设想的道路

有一种奇怪的想法：结点数和每个结点的边数不算很多，猜想可以建图，对于每个点，与相邻能通过的点之间有长为 $w$ 的边连接；如果此点是传送门点，则与其他传送门点均有长为 $a_i+a_j$ 的边连接。然后使用 Dijkstra 等单源最短路算法直接算出起点到终点的距离。

10. 树的优化

来源：Codeforces 682C

个人难度评级：6

问题描述

在一个原始森林里，有人发现了一颗根编号为 $1$ 的神奇树，它的每个顶点以及每条边上都标有一个数字。

然而，他发现这颗树上有些顶点有瑕疵，也称为瑕疵点。一个顶点 $v$ 被称为瑕疵点是指在它的子树中存在点 $u$ ，使得 $dist(v,u)>a_u$ ，这里 $a_u$ 是标注在顶点 $u$ 上的数字，而 $dist(v,u)$ 是所有标注在从顶点 $v$ 到顶点 $u$ 的路径上边的数字之和。

如果一个顶点只有一条路径相连，则这个顶点是树的叶子节点。但是树的根节点是叶子节点，当且仅当数树仅有一个单一顶点，即根节点。

这人决定删除一些叶子节点，直到整颗树不存在任何瑕疵点。那么，需要删除的叶子节点的最少数是多少？

输入形式

输入的第一行为一个整数 $n$ $(1 \le n \le 10^5 )$ 。

接下来一行为 $n$ 个整数 $a_1$ 、 $a_2$ 、…、 $a_n$ $(1 \le a \le 10^9)$ ，这里 $a_i$ 是标注在顶点 $i$ 上的数字。

接下来的 $n-1$ 描述了树中边的情况，第 $i$ 行有两个整数 $p_i$ 和 $c_i$ $(1 \le p_i \le n, -10^9 \le c_i \le 10^9)$ ，这意味着在顶点 $i+1$ 和 $p_i$ 之间有边相连，其上标有数字 $c_i$

输出形式

输出一个整数，表示需要删除的最少叶子节点数。

样例输入

9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8

样例输出

提示

以下是可能的处理过程

解题思路

这个题我做的时候觉得挺难的，主要是没读懂，而且这个题的弯绕得很多，所以给了 6 级。参考了【Codeforces 682C】Alyona and the Tree - AWCXV - 博客园 (cnblogs.com)。

我们设结点 $u$ 是在结点 $v$ 子树的叶子结点，如果 $dist(v,u)>a_u$ ，即它们之间的边权和大于 $u$ 点的点权，那么下面的 $u$ 就会让上面的 $v$ 伤心（原题说法，即瑕疵，这里习惯了不改了）。这时候，就要把下面的 $v$ 叶子移除，来让 $u$ 不因它伤心。

能让 $u$ 结点伤心的，并不一定是叶子结点，而是任何能满足边权和大于 $v$ 点权的 $v$ 结点，即使 $v$ 在中间；而只要让 $u$ 伤心，就必须移除 $v$ 。题面要求我们只能移除叶子结点，这样的话，如果子树中的中间结点 $v$ 让 $u$ 伤心，必须移除 $v$ 为根节点的整棵子树。这样是完全可行的，因为上面的结点伤不伤心，跟 $v$ 的子节点一点关系都没有，爱怎么移除怎么移除，不把下面的移除干净，导致伤心的 $v$ 的还没办法移除。

也正是由于 $v$ 下面的结点和上面结点是否伤心无关，我们可以知道：设结点对 $<u,v>$ 代表下面的 $v$ 让上面的 $u$ 伤心，如果 $<u,v>$ 相比 $<p,q>$ 更靠树的根部（也就是靠上），我们可以直接删除 $v$ 的子树，如果 $<p,q>$ 的关系因删除而不再存在，也并不需要在意，正好一起切没了。

这个时候，就可以想出一个并不是非常高效的算法（但应该能应付 CG，没实现，不保证）：

先使用一次 DFS，求出根节点和各结点之间的边权和 $dist(1,u)$ ，存储，因为 $dist(u,v)=dist(1,v)-dist(1,u)$ 。然后使用第二轮 DFS，将每个遍历到的结点作为 $u$ ，然后再以它为根节点向下进行一层 DFS，枚举它的根节点作为 $v$ 。检验 $u$ 是否会被 $v$ 搞伤心，如果会，直接删除通向 $v$ 的边，代表删除下面的整棵树，不会的话则继续搜索。最后再一轮 DFS 得到没被删除的结点数量，计算得到删掉的数量（或者在删除结点时，以被删掉的 $v$ 为起点 DFS 得到被删除的结点数量），输出。

注意到一个问题：对于任意结点 $v$ ，不管它造成了从 $1$ 到 $v$ 之间哪个结点不高兴， $v$ 为根的树都要被删除。如果我们记录从 $1$ 到 $v$ 以 $v$ 结尾的 ** 最大 ** 边权和，就不需要判上游的特定_某个_结点是否会被搞伤心（上面算法的思想），只需要一次判断，就可以得出上游_是否会有_结点被 $v$ 搞得不伤心，从而直接决定删不删掉 $v$ 。

那如何得出最大边权和呢？整个过程可以直接整合进一次 DFS 中，就是这个算法的核心。给 DFS 函数传入两个变量，当前结点 $u$ 的编号和最大边权和。如果最大边权和大于该节点的权值直接返回，不再搜索下去也不计数，代表这个点被删除。否则，没被删除的点计数 + 1，然后继续 DFS，分两种情况：如果当前最大边权和小于 0，则传入的最大边权和就是 $u$ 与子节点间的边权；否则，传入当前最大边权和 + 上述边权。这里使用了贪心的思想，来保证边权和最大，且以当前结点 $u$ 结尾。这一段结合代码来讲，就是这样：

        cpp
        
            if (dist> 0) //dist 是当前最大边权和
        {
            dfs(to[i], dist + weight[i]); // 链式前向星存边，边号 i，to[i] 是边的终点，weight[i] 是这条边的边权
        }
        else
        {
            dfs(to[i], weight[i]);
        }

1
2
3
4
5
6
7
8


        if (dist> 0) //dist 是当前最大边权和
        {
            dfs(to[i], dist + weight[i]); // 链式前向星存边，边号 i，to[i] 是边的终点，weight[i] 是这条边的边权
        }
        else
        {
            dfs(to[i], weight[i]);
        }

题中数据的输入方式已经表明了谁是更靠近根的节点，我们只需要存储有向边，不会出现下面的结点连往上面结点的边，也就不再需要打标记证明哪个结点访问过。