[置顶][差 4 题][2nd ucup] Warsaw 站选做

本来不想做 ucup 了，但是发现我好像也没有别的题能做（大雾。

比赛链接。

C. Cliques

题意

给定一棵 个点的树 和一个初始为空的图 。

进行 次操作，每一次操作为给图 加上或删掉一个点 ，满足 。

图 上的一个点对应了树 的一条路径，图 上两个点之间有边，当且仅当其对应的路径在 上有公共点。

在每一次操作之后，输出图 上有多少个子图是团。

，。

题解

有点脑瘫了哥们。

首先可以知道，两条链的交一定是一条链（可能为空），所以多条链的交也一定是一条链。

那么令 的根为 ，设 里一个团的『关键点』为其所有链在 中的公共点里，最靠上的一个。

那么考虑直接枚举 中的点，计算其是多少个团的关键点。

设有 条链经过了这个点， 条链同时经过了这个点和他的父亲，那么这个点的贡献是 。

带修的话直接上树剖就行，时间复杂度 。

提交记录。

G. Matrix Inverse

题意

给定一个矩阵 ，求出它的逆。

题目额外给出一个矩阵 ，保证 与 至多有 个位置不同。

。

题解

令 为 与 有多少个位置不同。

首先因为 过不了，所以我们甚至无法用矩阵乘法来判两个矩阵是否互为逆。

考虑一个经典 trick，我们随机一个 的矩阵 ，并且计算 。

如果 的话，那么大概率会有 。

否则如果有 ，那么就一定会有 。

同理我们随机一个 的矩阵 并计算 。

此时如果有 ，那么就一定会有 。

这样我们就能确定 个不同的位置在哪些行和列，现在我们有 个不确定的位置。

考虑 这个过程， 的第 行决定了 的第 行，而我们知道 。

那么我们直接对于 的 个关键行里面， 个关键列拿出来跑高斯消元就好了。

时间复杂度 。

提交记录。

K. Jump Graph

题意

给定一个长度为 的排列 ，现在有一张有向图。

图上存在边 当且仅当对于每一个 都有 。

对于每一个点 ，求出 到其他所有点的距离之和。

。

题解

考虑建出这个排列的笛卡尔树（大根）。

考虑对于一个点 ，来说，其左子树的点如果想要跳到右子树，那么第一步肯定是跳到 或者 。

（这是显然的，首先这个点得跳出这个子树，如果要跳出子树就只能往祖先跳，那么显然只会往 和 ，其他的祖先很不优）。

那么考虑先求出每一个点到其子树内点的距离和，但是容易发现这里有一点问题。

假设我们要从点 到其右子树内某个点，可能是直接往下走，也有可能是先跳到 再往下走，这不好办。

但是我们发现 这条双向边是存在的，也就是说对于 ，有 。

那么我们对于每一棵子树维护，以其整个区间的左侧一个极大点为起点，到整棵子树点的距离和是多少。

再额外维护，有多少个点，从左侧极大点的距离比从右侧极大点距离小，有多少个点相等，有多少个点右边小。

这样就能处理出大部分情况了，有少部分情况，子树左侧或右侧不存在极大点，可能需要特殊处理。

再预处理完每一个点到子树内的距离和之后，再递归一遍就能算出每一个点到子树外的距离和了。

时间复杂度 。

提交记录。

这题感觉写起来真的好煎熬好煎熬