2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest

菜得不行。

Problem A

Solved by ultmaster. 01:22 (+2)

题意：$a$, $b$, $c$ 是递增数列，求 $(i,j,k)$ 对数满足 $|a_i-b_j| \le d, |a_i-c_k| \le d, |b_j-c_k| \le d$。

题解：枚举 $a$ 中的元素，$b$ 中满足的显然是一个区间，对于这个区间内的数，满足的 $c$ 的右端点可以通过预处理得到。通过预处理前缀和应该不难解决。不过大概是做烦了，鉴于大家都过得飞快。

先写错了一个变量 WA 了一发，然后不知道什么地方崩了 long long（还立了个 flag 说绝对不会是这个问题的），被 zerol 全部改成 long long 过了。

Problem C

Solved by ultmaster. 03:19 (+)

题意：在树上找一个点集，使得每条路径都与这个点集有交集。

题解：如果树是一条链，显然是一个经典的「丽娃河装路灯」问题（之前还讨论过它的树状数组优化）。那么放到树上，我们就按照 LCA 的深度排序，路灯肯定装在 LCA 上。同样使用树状数组优化，加个树链剖分就可以。

Problem J

Solved by ultmaster.

题意：给一个数列。每次询问一个区间。问区间内的数组成的多重集有多少个子集的和是 $m$ 的倍数。

题解：离线。按区间分治。横跨两边的双向背包合并。否则递归。听起来很简单。

其实做的时候还是想生成函数优化就已经凉了。完全没有考虑离线。所以，划重点：离线。

Problem K

Solved by zerol. 02:56 (+3)

Problem L

Upsolved by ultmaster.

题意：给一个无向图，问给每条边加税后，分别会有多少个点从起点出发涨价了。转化一下就是说：给一个 DAG，问删掉每条边之后，各有多少个点从 DAG 的最左端不连通。

题解：显然对于入度大于等于 2 的点，它删掉任意一条入边都是不影响的。

考虑一种增量构造一棵树的方法：DAG 拓补排序之后，一个一个点加进来。对于某个点 $v$，如果入度为 1，即只有一条边 $(u,v)$，则将 $(u,v)$ 加入树中；如果入度为 $k$ ($k > 1$)，即存在 $(u_1,v),(u_2,v),\ldots,(u_k,v)$，则将 $(LCA(u_1,u_2,\ldots,u_k), v)$ 加入树中。这种做法的正确性在于：对于有多条边进来的点，只有所有这些分支都挂了它才到达不了；那么我们不妨直接将它和「所有分支」的公共祖先相连。

这样的话删边问题就转化成了树上删边问题（也就是说只有删树上的边才是有用的），删树上边造成的损失就是子树的大小。注意树上有些边是我们自己加的，这些边不能累计入答案。

这题面向标程编程了。LCA 都能写错我是不是傻逼？