首先跑最短路，本题并不卡那个死掉的算法。 求出 1 号节点到每个点的最短路 \(d\)。 然后考虑计数。 计数可以考虑 DP，但是必须满足无后效性。 设计一个类似于分层图的状态。 \(f(x,k)\) 为 1 号节点到 \(x\) 号节点，距离为 \(d(x)+k\) 的方案数。 考虑转移，假定 \(f(y,k_2)\) 能转移到 \(f(x,k_1)\)。 设 \((x \rig

经典树上差分。 考虑能观察到玩家的条件，不难发现，对于每个观察员 \(x\)，能观察到玩家 \(i\)，当且仅当满足 $ d(s_i)-d(x)=w_x$ $ d(s_i)+d(x)-2 d(lca(s_i,t_i))=w_x$ 上述两式可化为 \[ d(s_i)=w_x+d(x) \] \[ d(s_i)-2 \times d(lca(s_i,t_i))=w_x-d(x)

实际上就是 树网的核 的数据加强版。 原题暴力枚举即可，本题也可以用复杂度为 \(O(n\log SUM)\) 的二分答案，这里只讲述单调队列的 \(O(n)\) 算法。 题意：在树的直径上选择两个距离不超过 \(s\) 的点，最小化「偏心距」。 「偏心距」：树中距离直径最远的节点到直径的距离。 显然，可以用单调队列维护。 设直径为 \(u\)，其节点数为 \(o\)，直径上两点为

两次 DFS 求出树的直径。 显然多条直径必定交于至少一点，且包含它们的中点。 则若舍去他们交点之外的边，剩下的边即为所求。 设直径左右端点为 $ l, r$。 在第二次 DFS 时能够求出 $ l$ 到直径每个节点的距离，所以从 $ r$ 向 $ l$ 遍历。 对于直径上的每个点 \(i\)，分别求出在不经过直径上其他点的情况的，所能达到的最远距离，记作 \(d\)。设它到直径左端

考虑 DP。 DP 需要一定的顺序。因为给出的矩形没有包含的关系，所以我们按照每个矩形右上角点的横坐标 \(x\) 递增排序，那么纵坐标 $ y$ 一定是递减排序的。 设 \(S_i = x_i \times y_i\)。 因为每个矩形都有选与不选两种选择，所以设 $ f(i)$ 为在排序后的 \([1,i]\) 中，必须选择第 \(i\) 个矩形获得的最大收益，也就是选出的矩形面积

我最喜欢的紫色水题（ 给出一个森林，有两种操作。 询问某个点所在的树的直径 在两个点所在的两棵树间连一条边，最小化其直径 显然的，对于第一种操作，DP / DFS / BFS 预处理直径，并查集维护每棵树的点就行了。 问题在于高效维护第二种操作。 不难想到，两棵树之间连一条边，相当于合并两个集合。 而最小化新树的直径，显然要在两树直径的中点处连边。 证明： 反证法。

update 2022.2.9 修改了代码 不妨假设平民为白点，杀手为黑点，认识的关系为一条有向边。 求不访问黑点并且知道黑点的最小代价。 若有 \(n\) 个点，显然每个点为黑的概率为 \(\frac{1}{n}\)。 而每访问一个白点，都能得知与它出边相连的点的颜色。 考虑强连通分量。 不难发现，对于每个强连通分量，只要以概率增加 \(\frac{1}{n}\) 为代价访问其中

有东西被加密了, 请输入密码查看.

设 \(p\) 为质数且 \(p \le n\)。 显然的，若 \(\gcd(x,y)=1\)，则 \(\gcd(x \times p,y \times p)=p\)。 问题转化为求互质的数对 \((x,y)\) 的个数。 这时候就要用上欧拉函数了！ 由于欧拉函数是与一个数互质，那么用前缀和。 由于 \((x,y)\) 与 \((y,x)\) 算两种，所以计数时要乘 \(2\)。 设

本文重写于 2023.9.1 朴素的状态就设 \(f(i,j)\) 为考虑前 \(i\) 个数，选出了 \(j\) 个数的方案数。 有转移 \[ f(i,j) = \begin{cases} f(i-1,j)+f(i-1,j-1) & j \mid a_i \\ f(i-1,j) & j \nmid a_i \end