7 月做题记录

R7-07-07 07:07:07???

0630T2 - P3549 MUL-Multidrink Ult

题目大意

TL：1s，ML：128MB

给定一棵个节点的树，要求构造出一种遍历方案，使得：

同一个点不能被遍历两次

要求输出，或判断无解。

。

解答

我记得之前做过一道非常像的题，CF1819C，感觉这两道题不能说是一模一样，只能说是毫无关系。现在开始讲做法。

我们可以现在树上把的这一条链给拎出来。把这条链的边全删了之后，剩下的节点就全部都变成了很多个小子树。并且我们发现，如果有解的话，就一定存在一种解，使得可以按照在链上的顺序依次把每一个子树解决完。

那么从前往后解决，跳以为根的子树的话，就会遇到这几种情况：

从跳入，遍历完后从跳出。
从跳入，遍历完后从的其中一个儿子跳出。
从的其中一个儿子跳入，遍历完后从的其中一个儿子跳出。
从的其中一个儿子跳入，遍历完后从跳出。

我们发现情况 3 其实就是情况 1 的逆向版，所以可以合并为 3 种情况。

然后我们可以 DP 解决：设为可否以为根，满足情况（若满足那么就满足）。那么就可以开始分类讨论：

这个情况的条件就是是叶子节点即可。
这种情况则可以先跳，然后跳其中一个不是叶子节点的子树，遍历完子树之后再跳出跳到的其它叶子节点上，最后从其中一个叶子节点跳出。

所以条件就是：至多只有个儿子不满足且这个要满足（即）。其它儿子都要满足。
先跳的叶子节点。这种肯定不劣。然后看有多少个不是叶子节点的子树。
1. 若有个，那么跳完叶子后就先跳到，然后（逆向），遍历完后跨过跳出去。
2. 若有个，令另外一个儿子为，则跳完的叶子后先，然后跳到，之后从开始，最后跨过跳出去。
3. 若有个，因为是不会给你用次的，所以无解。
所以条件就是：至多只有个儿子不满足且这些要满足。并且如果有个儿子，那么就不行。

这样就可以用 DP 把所有的子树求出可以怎么进怎么出了。

然后因为是要在链上按顺序遍历所有子树的，所以我们再记录一个表示：

：遍历完链上的前个点的子树，最终停在链上的第个点是否可行。
：遍历完链上的前个点的子树，最终停在链上的第个点的其中一个儿子是否可行。

然后就可以转移了（为链长）。初始值设。第个点从第个点的状态转移过来也分种情况（这里令为点的儿子，为点）：

。因为你是从的儿子出来的，所以之前也被遍历过了。并且因为距离，所以最终只能跳到上。

所以条件就是令成立才行。g[i][0] |= g[i-1][1] & f[cur][0]
。这里因为跳的距离，所以可以选择跳到上或者跳到上。

所以条件就是令或者成立都行。g[i][0] |= g[i-1][0] & (f[cur][0] | f[cur][1])
。还是，你只能跳到上。

所以只能令才行。g[i][1] |= g[i-1][1] & f[cur][1]
。还是，你可以选择跳到根上或者儿子上。

所以令或者成立都行。g[i][1] |= g[i-1][0] & (f[cur][1] | f[cur][2])

然后就可以根据 DP 转移来从后从后往前使用 DFS 加上之前的两个 DP 数组记录答案了。无解就是的情况。

代码写了 7.38K，其中 1K 模板，1.3K 注释，核心代码也是挺长的。原题上过了，但是联考题他开 + 256MB 卡我空间，就是非常没有素质你知道吗。我已经不打算改了。

0701T2 - XOR and Inversion Ult

题目大意

TL：2s，ML：128MB

给定的排列，下标从开始，次操作，每次操作形如以下两种中的一种：

1 x: 将排列中的每个元素替换为。
2 x: 重新排列。对于每一个下标，操作后下标处的新元素是操作前下标处的元素。

其中表示按位异或运算。操作有后效性。每次操作后，求出整个序列的逆序对数。

本题有多组测试数据。

解答

我们发现，所有的 1 操作是可以合并的，所有的 2 操作也是可以合并的。令之前 1 操作的的异或和为，2 操作的的异或和为，所以就相当于是先给原序列做了个的 1 操作，然后再做的 2 操作，最后求答案，并且无后效性。

考虑，即只做 1 操作的情况。我们先单拎出来两个数，我们令和的最大的不同的二进制位为，那么当的第位为时，那么和就会在顺序对和逆序对之间转换状态。

那么我们就可以统计为时的逆序对（）、顺序对（）个数。最后枚举位，然后再根据的每一位统计答案即可。统计使用桶统计即可。

考虑，即只做 2 操作的情况。这里则是下标替换。那么我们就可以统计时的逆序对、顺序对个数。然后再根据的每一位统计答案即可。然后还是使用桶。

然后现在有了两维。那么我们就要统计为的逆序对、顺序对个数。这里就不能只用桶统计了，因为有两维。其实我们可以对下标进行分治，即对进行分治。我们定函数 solve(bit, l, r) 为合并和区间，并且和这两个区间的。因为你的排列元素是，所以长度一定是的整数次幂，随便手玩一下也可以发现这个第二维是对的。现在就相当于是消去了第二维，然后就只用算第一维在和之间产生的贡献了。然后初始直接 solve(n-1, 0, (1<<n)-1) 然后分治就完了。

然后就可以在线解决了。枚举和，根据和的每一位统计答案即可。预处理分治时间复杂度，查询总时间复杂度。这道题到这里基本就做完了。

后面就是一些优化。因为空间限制 128MB，所以我们可以对桶进行一些优化：考虑到的时候的桶是怎么写的。我们维护的是在区间内右移位后值为的值有多少个，这样就方便统计不同位首位为第位的数的个数了。传统的静态数组的大小为，为，我只是说有可能爆。这里优化可以使用动态开点，使得 ……能使空间复杂度达到。

具体可以这么实现：

int *tong[L]; // * 号不要忘
...
void Maisolve(){
    ...
    for(int i=0, siz=1<<n; i<n; i++, siz>>=1)
        tong[i] = new int [siz]();
    // new 后面跟你要开的数组的元素类型，[]里面写数组大小。
    ...
    for(int i=0;i<n;i++) delete[] tong[i];
    // 删除数组元素。
}

0702 好题 - CF1815D XOR Counting 2600

题目大意

TL：2s，ML：250MB

记表示按位异或运算。
给定整数。
记一个序列是好的，当且仅当它是一个长度为的非负整数序列，且其元素之和恰好为。
求在好的序列中，的所有可能取值之和对取模后的值。
对于一个的可能取值，无论有多少个可以取得这个值的好的序列，这个值都应只被计入所求之和一次。
每个测试点包含组数据。

解答

私人诈骗。但题很好。

首先对分类讨论。

，显然。
，假如你想让原序列的异或和为，那么你可以构造序列。所以这种情况的异或和集合就是所有并且和奇偶性相同的非负整数。
。就是让你求给你两个数，，问不同种类的的和。

我们可以使用递推：设为时的答案。那么就可以根据最后一位分类讨论：
- 为奇数，即最后一位为，那么分配情况就只能是 1 奇 1 偶了。那么可以发现和有关。但是因为是 1 奇 1 偶，所以最后一位还要多出来个 1。所以还要统计，即时有多少种不同的异或和。于是就可以构造递推式：
- 为偶数，即最后一位为。那么就有两种分配情况：
  - 2 偶，此时可以直接从状态转移：。
  - 2 奇，因为借了位，此时就要从状态转移：。
  每项转移的时候就把这两个玩意加起来就可以。
最后的答案就是。

分析一下复杂度：当为奇数的时候，直接转移没错。而当为偶数的时候，从和转移过来，容易发现是一个奇数一个偶数的。若为奇数，那么它的下一层递归就会是，就会和的下一层状态并到一起。若为奇数，那么它的下一层递归就会是，就会和的下一层状态并到一起。所以时间复杂度正确，为。这里空间的话我开的 map，个乘上可以过。

0702 好题 - CF1227G Not Same 2600

题目大意

TL：2s，ML：250MB

给定大小为的序列，满足。

你需要执行至多次操作使得所有数变为，每次操作你可以把一个子集的元素都，要求每次操作的子集互不相同。构造出一组方案。。

解答

有一种构造方案。可以先给从大到小排序，然后设这个是从大到小第个数，那么这一列就从第行开始。然后一直往下填个空。到底了就从第 1 行开始往下填。最后交换列使其符合原来的的大小关系。

这样为什么是对的呢？考虑反证法。因为交换列后是相等的，所以交换列前也是相等的。这里考虑。

假设现在第行和第行完全相同（），那么此时因为一定是，所以此时一定是，所以在第列，有的范围就被限制在了行里了。

然后看第列，那么有的范围就被限制在行里面了。所以此时一定为，所以此时也是，所以有的范围就被限制在了行里了。

然后看第列，范围 ……最后到第列的有范围就变为了。但是因为，所以一定是，与之前推出来的不符合，所以假设不成立。构造的正确性得证。

0702 好题 - P6782 [Ynoi] rplexq

题目大意

TL：1s，ML：128MB

给定一棵个节点的有根树，第个点的编号是。

有次询问，每次询问给出，求有多少点编号的二元组满足且和的最近公共祖先是节点。

，。

解答

对于一些题啊，我只能说他的【数据删除】了也不自知。

首先，这道题可以转化成如下形式：令里面的所有点在的子树中出现次数为，那么就要喊你求。就相当于是做个容斥。那么就可以对每一个分情况讨论：

当时，可以使用二维数点来做：就相当于是让你求，DFN 序在一段区间、下标序列在一段区间的二维数点。使用分块数据结构可以使复杂度为。但是如果直接用普通的存询问方式的话你的空间会，炸！但是这道题有一个非常好的性质：就是对于一个，所有的区间是不交的。所以同一个的所有区间可以共用一个下标，并且存询问只用在节点上存，然后遍历树的时候就查这个点的父亲就可以了。这样空间就压到了，线性。
当时，能想到的最暴力的方法就是，对于所有相同的询问，先暴力遍历所有子树，给所有子树染色，再使用莫队 + 对每一个颜色开一个桶统计。这样做固然可以，但是每一次的复杂度，炸！所以，可以再把第一种方法用回来，也就是给前个重儿子使用第一种方法，其它儿子使用第二种方法，这样的时间复杂度就是，因为取的是前个重儿子，所以是对的。但是为了保证复杂度，就不能在原序列上跑莫队，应该将每一个离散化后再跑，所以就是。

然后是一些杂谈，这道题的思路清晰，代码比较好写，但是非常难调。从 2 号晚上写完了就开始调调到了 3 号早晨。另外，我把这个取到没有过这道题，取到时过了，取到时跑到我的所有提交里面的最优解。

[续] 线性基专题

P4869 albus 就是要第一个出场 Mas

题目大意

TL：1s，ML：128MB

已知一个长度为的正整数序列（下标从开始），令，的幂集定义为所有子集构成的集合。定义映射。

现在 albus 把中每个集合的值计算出来，从小到大排成一行，记为序列（下标从开始）。

给定一个数，那么这个数在序列中第次出现时的下标是多少呢（对取模）？

其他所有输入均不超过

解答

这道题的题面用人话说就是，你有一个序列，将这个序列的每一个“子序列的异或和”（包括空序列）提取出来形成一个新序列，将从小到大排序，然后问数在序列中，第一次出现的下标模某个数的值。

异或和可以想到线性基，然后假设这个线性基有个元素，那么可以异或出来个值嘛，那么每一个值会出现次。理由如下：你其它数不在线性基里面是因为可以被线性基里面的数表示，也就是可以被里面的数异或为。这个时候去异或其它数自然也就是其它数了。因为有个这样的数，所以会出现次。

然后我们现在就要求在那个值里面有多少个值在前面。线性基里面第位有值（前面有个比在线性基上的第位小的值）就说明，如果数的这一位也有值，那么一定有个数比小，所以就可以按照这个统计。最后会得到一个。

最终答案就是。

P4839 P 哥的桶 Mas

题目大意

TL：2s，ML：500MB

P 哥现在有个桶，它们排成了一排，这些桶可以装下任意多个球。每个球有一个固定的价值。

P 哥时不时地会找新球，并把新找的球丢进某个桶里面。我们用来表示 P 哥找了一个价值为的球，并且丢进了号桶里面。

P 哥每次会在特定的桶里面拿出一些球。我们用来表示 P 哥在号桶到号桶之间拿球。P 哥希望拿出来的球的价值异或和尽可能大。

注意：P 哥拿出这些球后会把它们物归原位。

，，，。

解答

线段树上线性基修改、合并。可过。做法有，但是用的是猫树分治，不会。

P11620 [Ynoi] TEST_34 Mas

题目大意

TL：3s，ML：125MB

给你一个长度为 n 的整数序列 , , , ，你需要实现以下两种操作，每个操作都可以用四个整数来表示：

时，代表把一个区间内的所有数都 xor 上。

时，查询一个区间内选任意个数（包括个）数 xor 起来，这个值与的最大 xor 和是多少。

，值域在之间

解答

这道题似乎是非常简单的 Ynoi。

我们发现，令，那么每一次区间的时候就可以只和。然后对于区间查询，我们可以发现，在区间中选出来出来异或就相当于是取出来异或。所以区间的线性基可以通过插入和来取得。后者可以通过线段树维护，前者因为要支持区间修改单点查询，所以就用数组加上树状数组就可以实现。时间复杂度还是，依然可以过。

P5607 [Ynoi] 无力回天 Mas

题目大意

TL：1s，ML：512MB

你需要维护编号为的个集合，初始为空。

共次操作：

给定，在编号的集合插入，保证之前不在这个集合中；
给定，问编号的集合的并的元素个数。

对于的数据，满足，；

解答

首先，。我们就求两个元素的交的大小。

这道题可以想到类似根号分治状物，但是如果根据集合的被插入次数根号分治那么你就会死，因为后面思路无。正解是根据元素的插入次数对元素根号分治。

对于插入次数的所有元素，可以分析出这种元素不超过种。那么我们可以对所有集合开一个大小为的 bitset，将这些元素搞个映射，然后就可以插入、查询。

然后对于插入次数的所有元素，我们可以使用 vector 存，里面就存元素被插入到了哪些集合里面。然后每次插入一个元素的时候，我们就遍历这个然后计算集合之间的贡献。然后我们使用一个哈希表来存只考虑插入次数的集合的交的大小。所以这样的话就可以做到，理论上的修改复杂度为，查询。

然后就是卡常。首先如果你的第一种分治，直接使用的 bitset 你的空间就会死。你可以先存第一个元素，然后当有两个元素的时候再开 bitset（依然要做映射）。这样你的空间复杂度就变成了。

然后看第二种分治，因为 map,umap,gp_ht 的逆天跟 XL TECHNO -More Dance Remix- 一样大的常数，所以这里要使用手写哈希表。并且要给手写哈希表做对第一维的优化：先遍历询问（这里令所有的），然后对每一个记录它出现的次数。因为哈希表是二维插入二维查询，所以我们把第一维的每一个不同的分开，然后令这个次数为每一个的。并且还要记录偏移值免得重合。并且为了时空复杂度，我们只对出现在询问里面的进行操作，其它的都不做。这样可以卡过。

然后当的时候我跑的最快，可以过。

?T1 - P9844 Paimon Segment Tree Exp

题目大意

TL：4s，ML：256MB

给定数列，并进行次操作。操作包含3个参数, () 和，代表对该序列第到第个元素加上。

记为次操作后的值。注意若未被修改，则的值与相同。定义是的初始值。

完成所有操作后，荧进行次询问，询问包含4个整数, , and ，派蒙需要回答

$\sum\limits_{i=l_k}^{r_k}\sum\limits_{j=x_k}^{y_k} a_{i, j}^2$

请将答案对取模后输出。

解答

差分询问，将其变为，所以问题就变为了求区间的历史平方和。对于这玩意的第一反应就是线段树。

然后后面是我没想到的：线段树维护矩阵。每个矩阵维护个元素，分别代表：区间长度，区间和，区间平方和，区间历史平方和。然后每次更新的时候，考虑式子：

$\begin{aligned} A &\gets A\\ B &\gets B+Av\\ C &\gets C + 2Bv + Av^2\\ D &\gets D + C + 2Bv + Av^2 \end{aligned}$

然后就可以根据矩阵乘法构造矩阵来乘了。因为这玩意是满足结合律的，所以 lzytag 使用矩阵维护完全没问题。

同时也不要忘了给剩下的区间执行的矩阵乘！

~~这是 M4T21X 第一次出现在我的代码里面~~

NOIP Mas 题训练

P11364 2024 树上查询 Mas

题目大意

TL：2s，ML：1GB

给定一棵个结点的有根树，根结点编号为，每个结点的深度定义为到的简单路径上的结点数量。

除此之外，再定义为编号在中所有结点的最近公共祖先，即的公共祖先结点中深度最大的结点。

小 N 对这棵树提出了个询问。在每个询问中，小 N 都会给出三个参数，表示他想知道中任意长度大于等于的连续子区间的最近公共祖先深度的最大值，即

$\max_{l\le l'\le r'\le r \land r'-l'+1\ge k}\text{dep}_ {\text{LCA*}(l', r')}$

你的任务是帮助小 S 来回答这些询问。

解答

因为一个区间，往外扩展的元素越多，公共 LCA 的深度就会越浅，并且众所周知，，所以我们对于每一个区间，求一个代表能使公共 LCA 深度为可以扩展出的最大区间，其中就是刚刚所说的深度。然后就得到了个支配区间了。

然后现在就要求和交集至少为，最大的。然后可以推出以下不等式是交集至少为的充要条件：

$y \ge r \land l \le r-k+1\\ l+k-1\le y\le r \land y-x+1 \ge k$

然后做两次扫描线取。这里我是第一个不等式对做扫描线，第二个不等式对做扫描线。即可过此题。

P3960 2017 列队 Mas

题目大意

TL：2s，ML：500MB

前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有名学生，方阵的行数为，列数为。

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从到编上了号码（参见后面的样例）。即：初始时，第行第列的学生的编号是。

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天中，一共发生了件这样的离队事件。每一次离队事件可以用数对描述，表示第行第列的学生离队。

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达这样的两条指令：

向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条指令之后，空位在第行第列。
向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条指令之后，空位在第行第列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后，下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第行第列一个空位，这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学的编号是多少。

注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后方阵中同学的编号可能是乱序的。

解答

因为修改最多只有次，并且手玩样例或者分析题意可以发现，当离队的时候，每次第行插入的元素都是最后一列的第个元素，然后最后元素又会插入到最后一列的最后去。所以可以使用平衡树暴力维护最后一列。

但是因为元素个数太多，你是不可能每一行都开一个暴力维护元素的平衡树的。还是利用修改最多次。而且原序列有一个性质，可以把每一行分为两部分：原有的部分和插进来的其他地方的部分。插进来的其他地方的部分就可以使用暴力维护，因为你这些部分的点数最多个，时空复杂度可以接受。然后对于原有的部分，因为你是在这些部分删除数，所以可以维护删掉的数在原本序列的位置。

每删一个位置，如果在前面那部分就先得到的排名，根据排名算出元素；然后将插入每一行维护删掉的数在原本序列的位置的平衡树，并且将所有大于的元素都。如果在后面那部分就暴力维护。并且删掉前、后任一部分都要在后面的那部分的最后插入数。然后如果特判。

这道题不好，使我调 3、4 个小时调到半夜。然后调完了之后就去点外卖吃羊肉串去了。羊肉串好吃。

P1084 2012 疫情控制 Mas

题目大意

TL：2s，ML：128MB

H 国有个城市，这个城市用条双向道路相互连通构成一棵树，号城市是首都，也是树中的根节点。

H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。

现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

保证军队不会驻扎在首都。

，。

解答

哦对，我要去下歌了，上次打杂音均衡器搞到两首好歌去把他们下下来。稍等。

这道题的话假设可以在个小时内可以完成，那么在这个小时内这些军队肯定会尽量往根上面移动。因为这样的话能够覆盖的叶子节点就会更多。我们将这些点分为两类：能够到根上面的点和不能到根上面的点。

对于那些不能到根上面的点，我们使用倍增求出它们最终会到达哪些点。然后对这些点按照 DFN 序排序，排序之后遍历它们会覆盖哪些叶子节点（要打 vis 标记，所以要按照 DFN 序排序）。然后对于那些没有被覆盖的叶子节点，求出那些叶子节点属于根的哪一个子树。然后就会得到一个序列（是没有还没被覆盖的叶子节点，则是有）。

这个时候，就是已经到根上面的结点发挥作用的时候了。对于每一个节点，到了根之后肯定有属于它自己的可移动距离。首先，因为不能驻扎军队，所以每一个点要么就在它自己归属的子树的最上端，要么就跑到其它子树的最上端。对于那些为的子树，那么原本在这些子树的所有能到根的节点去别人的子树肯定是不劣的。而对于那些为的子树，是有可能让从这个子树里面的可移动距离最小的就守在这个子树里面的。具体条件是什么呢？就是当这个可移动距离最小的点的可移动距离小于这个子树到根的边权的时候，它就必须驻守在这个子树里面并把序列的改成。

现在有了其它的点了。你就对这些点的可移动距离排个序，然后对插入。如果插入不了那么这个就不行。而如果插完了那么就行。所以这个是可以二分的。每一次 check 的时间复杂度为，所以总时间复杂度就是。

哦对，还有判无解。这个比较明显吧，就是当且仅当点数小于根的子树个数的时候无解。

P3959 2017 宝藏 Mas

题目大意

TL：1s，ML：250MB

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了个深埋在地下的宝藏屋，也给出了这个宝藏屋之间可供开发的条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是。其中代表这条道路的长度，代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

，，

解答

想的时候没有看到，想了半天。~~结果最后看到了之后还是没有想出来。~~

因为，所以可以使用状态压缩 DP。我们设从挖进去。因为最终肯定是一棵以为根的有根树嘛，并且一条道路的代价的其实就是深度（令根节点深度为），所以可以设为当前树的最大深度为，这棵树的点集为所需要的最小花费。

然后就可以列转移方程：

$dp_{i, S\cup T} = dp_{i-1, S} + cost(S, T) \times i.(\text{Here }S \cup T = \emptyset)$

其中为散点集想要和连通块点集连通所需连的边的最小花费。这个可以预处理。然后取所有转移中的最小值。初始值赋，最终答案则取。

那么有人就要问了，如果你这个里面包含了连向深度为等等的点的边又该如何呢？其实，因为我们是取的最小值，假设有一个点连向了深度为的点，那么其实从转移比从转移其实是更优的。因为前者的连的那条边乘的系数，后者乘的系数，所以后者会被前者给覆盖掉。

并且，因为设的，所以每一个都要试一遍，取最小值。时间复杂度。

P7962 2021 方差 Mas

题目大意

TL：1s，ML：512MB

给定长度为的非严格递增正整数数列。每次可以进行的操作是：任意选择一个正整数，将变为。求在若干次操作之后，该数列的方差最小值是多少。请输出最小值乘以的结果。

其中方差的定义为：数列中每个数与平均值的差的平方的平均值。更形式化地说，方差的定义为，其中。

测试点编号

解答

看，光从原来看的话应该是看不出什么的。但是换成差分之后应该就很明显了：

：。也就是说相当于是交换了两个差分。然后就可以开始化式子了：

。

令差分。

因为根据定义，方差只和每一个数和平均值的差有关，所以我们可以将所有数均减去，则：

$\begin{aligned} n^2D &= (n\sum (a_i-a_1)^2) - (\sum(a_i-a_1))^2 \\ &= n\sum_{i=1}^{n-1}(\sum_{j=1}^{i}d_j)^2 - (\sum_{i=1}^{n-1}\sum_{j=1}^{i}d_j)^2 \\ &= n\sum_{i=1}^{n-1}\sum_{j=1}^{i}\sum_{k=1}^{i} d_j\cdot d_k - (\sum_{j=1}^{n-1}d_j\cdot(n-j))^2 \\ &= n\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}d_j\cdot d_k\cdot(n-\max(j, k)) - \sum_{j=1}^{n-1}\sum_{k=1}^{n-1} d_j\cdot d_k \cdot (n-j)(n-k) \\ &= \sum_{j=1}^{n-1}\sum_{k=1}^{n-1}d_j\cdot d_k\cdot (n^2-n\cdot \max(j, k) - n^2 + n(j+k)-j\cdot k) \\ &= \sum_{j=1}^{n-1}\sum_{k=1}^{n-1}d_j\cdot d_k \times (n-\min(j, k) - j\cdot k) \\ &= (\sum_{i=1}^{n-1} d_i^2\cdot i\cdot (n-i) )+ 2\sum_{j=1}^{n-1}\sum_{k=j+1}^{n-1}d_j\cdot d_k\cdot j(n-k) \end{aligned}$

可以发现最后一个式子的前面部分是固定的，要想让其取到最小值就要让后面的式子最小。因为可以发现越靠近中间越大，那么差分数组应该呈先下降后上升趋势。

又因为，所以。然后就可以开算了。

这里使用原式子算（此处已经全部减去）。然后先让从小到大排序，然后选择插入这个下降-上升中间的分割线的左边还是右边。这玩意很容易 dp。设为考虑，所有和为的最大的。然后开始转移（令）：

若插入左边，则。
若插入右边，则。

然后初始设，。每次的枚举范围从，这里指的是当前更新到的最大的，并且随着转移实时更新。

然后最后的答案就是。时间复杂度。最后一个点的战斗时间 2:01.

为了优化时间复杂度，可以看限制：因为，所以的情况最多就种。所以可以跳过前面的转移，只运行的转移，并且数组可以优化掉第一维。时间复杂度。

P2435 染色 Mas

题目大意

TL：2s，ML：125MB

有一个行列的格点图，你需要给每个点上染上种颜色中的一种，要求没有两个相邻点颜色相同。给定第一行与最后一行的染色，试求总染色方案数。

答案对取模。

测试点编号

对于的数据，。

请注意，的值没有同时达到最大数据范围。

解答

对于其它数据点，因为，所以可以使用的轮廓线 DP 通过。

对于号数据点，根据判一下第一行和最后一行是否相等或相反即可。

P3547 [POI] CEN-Price List Ult

题目大意

TL：1s，ML：128MB

在这个国家的个城镇中，有对城镇由 Byteotian State Railways (BSR) 的轨道段连接。

直接通过铁路连接的任意两个城镇之间的票价为比特勒。

目前，Byteotia 的交通市场正在发生变化。

截至目前，BSR 面临着一个新的竞争对手：Byteotian Airlines (BA)。

BA 计划在一些城镇对之间运营航班。

由于 Byteotian 铁路相当舒适，BA 董事会决定只在那些没有直接铁路连接的城镇对之间运营航班。出于经济原因，BA 只会在那些需要恰好一次换乘的城镇之间飞行。

每张此类航班的票价为比特勒。

为了帮助 Byteotia 的市民规划他们的旅行，Byteotian 交通部 (BMT) 决定发行传单，说明所有可能城镇之间的最便宜路线。任意数量的直接铁路或飞机连接的序列被称为路线。名叫 Byteasar 的 BMT 官员被委派准备传单的价格表。

你能帮他写一个程序来确定正确的价格吗？

让我们明确一下，Byteotia 的所有连接，无论是铁路还是飞机，都是双向的。

标准输入的第一行包含五个整数，，，，和 (, , , )，以单个空格分隔。

数字和分别表示 Byteotia 中的城镇数量和直接铁路连接的数量。

为简化起见，我们将 Byteotia 的城镇编号为到。其他数字表示： - 需要确定连接价格的源城镇的编号； - 直接铁路连接的价格； - 直接飞机连接的价格。

接下来的行中的每一行包含一对整数和 (，对于 )，以单个空格分隔，指定由轨道直接连接的城镇对的编号。

你可以假设所有城镇都可以通过铁路从编号为的城镇到达。

解答

首先，答案只有可能是以下三种情况（令为的最短路距离）：

只坐铁路。答案就是。
先坐飞机，然后最后可能会坐铁路。乘坐路线就是最短路路线。答案就是。前两种情况均可以使用 BFS 或 Dijkstra 解决。
全部坐飞机，根本就不坐铁路。这种就不能直接算了。

先考虑暴力，可以 BFS，设当前被遍历到的点为，然后枚举的每一个出点，再枚举的每一个出点。然后看是否有边。若无边，那么就更新答案，并将 push 进 queue 里面。时间复杂度。

然后再想，因为你第一次被更新到答案的时候，后面它被更新时的答案就已经没有它第一次被更新的时候优了。也就是说，边已经在枚举第二条边方面上面已经没有用了。可以删除。或者说，此时你可以把连接的所有边在枚举第二条边方面上面废了。但是枚举第一条边的时候还没废，不能删。所以这里我枚举第一条边用 vector 存，枚举第二条边用带 pre 的链式前向星存，这样就可以删边了。

然后对于时间复杂度，我们设为中转边，那么优化后的时间复杂度就是，又因为。所以时间复杂度可以接受。

P4234 最小差值生成树 Mas

题目大意

TL：3s，ML：256MB

给定一个点标号从到的、有条边的无向图，求边权最大值与最小值的差值最小的生成树。图可能存在自环。

，，，。

解答

令这个差值为，发现这个具有可二分性，可以考虑二分。

我们定某条边边权为最大值，那么就可以得出有哪些边可以被加入了，这些边边权要满足。然后看这些边是否可以使所有点连通。若是，则满足。

因为这些最多就只有个，所以我们可以先把所有边边权从小到大排序，然后可以发现，将看作以边边权为最大值的合法边集合，那么每一条边出现的范围是一个区间，即会在出现。这个呢就可以通过单调队列（是这个东西吗？）来求。

然后这个东西就可以使用线段树分治来解了。就看是否有一个能使得连了这些边之后整个图连通。

时间复杂度。前者插入，第二者为时间复杂度瓶颈：可撤销并查集，第三者则为二分。时限 3s，洛谷神机可过。~~（其实好像不用神机也可以过的）~~

线头 DP 问题

大佬的线头 DP 的教程

P5999 [CEOI] kangaroo Mas

题目大意

TL：1s，ML：128MB

有一个园子，里面有个草丛排成一排，标号，有一个袋鼠，从出发，每次跳一步跳到一个其他的草丛，经过每个草丛恰好一次，最终到达。显然他会跳跃次。为了不被人类发现，袋鼠每次跳跃的方向必须与前一次不同。

具体地，如果他现在在，他是从跳跃一次到达的，然后他跳跃一次到达：

那么如果，就必须有；
如果，就必须有。

问从到的方案数模的结果。

两个路线不同，当且仅当草丛被访问的顺序不同。

保证至少有一种方案。

初始时可以往任意方向跳。

对于的数据，，

解答

我们令为将中的数全部考虑，个连通块（线头）的方案数。

先不考虑和的限制，考虑以下种转移：

一个连通块里面插入数（延续连续段）：这种操作不行。因为这里加数是从小到大加的，如果插入，后面再插入一个比它大的，那么就违反了题目要求。
两个连通块间新建一个块（新建连续段）：完全可以。因为个连通块有个空（包含首尾），那么。
两个连通块通过这个数合并（合并连续段）：也完全可以。因为两个连通块的首尾都比这个数小（可以根据加数顺序得到），所以，合法。因为个连通块有个空（不包含首尾，因为包含首尾就不能满足），那么。

现在考虑包含的限制。

当时，一定会插入到开头或是合并至开头（因为后面不会再让数跑到开头去的，所以放心）。。

当时，一定会插入到结尾或是合并至结尾（同理，后面不会让数合并至结尾）。。

当时，根据上文所说，不能让数跑到开头去了，所以。

当时，同理，。

总结可得：。

使用 DP 从小到大枚举，最终答案就是。

P9197 [JOI] 摩天大楼 Mas

题目大意

TL：2s，ML：512MB

将互不相同的个整数按照一定顺序排列。

假设排列为，要求：。

求满足题意的排列的方案数对取模后的结果。

对于所有数据，，，。

解答

因为，所以非常之好，可以使用线头 DP 狂暴设状态，思路越能靠近线头 DP 的思路越好。

令代表现在考虑，有个连续段，当前答案为，头是否被固定、尾是否被固定。为了更好地统计答案，我们将从大到小加入，然后考虑此时每次的变化。当每插入一个数的时候，可以被表示为如下：

然后当有的时候，那么因为左边或者右边没有线段了，那么就只能。

初始设置。

那么就可以开始考虑以下种转移：

延续连续段：每次在一个段的左或右边添加数，那么空就有个。。然后从的情况单独解决。
插入连续段：每次在空中添加数。那么空就有个。。然后从的情况单独解决。
合并连续段：每次合并两个连续段。那么空就有个。。

最后答案就是。写比较容易，调因为我漏了几种情况所以调了八百万年。

P7967 [COCI] Magneti Mas

题目大意

TL：1s，ML：512MB

给定个磁铁和个空位，其中相邻空位之间的距离为，每个空位可放置一个磁铁。所有个磁铁都必须被放置。每个磁铁可以吸引距离小于的其它磁铁。

求所有磁铁互不吸引的方案总数对取模的结果。

对于的数据，，，。

解答

为了更好地分辨，这里称题目中的「空位」为点。

我们可以把这道题先看成两部分：第一部分是将所有磁铁按照自己定的顺序紧密排列到点上，第二部分是将剩下的那些点插入这个空位中间。

对于第二部分，设某一种紧密排列所占用的点个数为，那么余个点。要将其插入个空位中间（每一个空位可以插入个），一共有种方案。这样我们就只需要算了。这里令为使得紧密排列后占用点个数为的排列的方案数。

我们依然设为考虑前个磁铁，形成个连续段，此时占用空间为，是否确定头、是否确定尾的方案数。为了更好转移，这里先给所有磁铁按照从小到大排序。这样后面的就不用考虑前面的限制了。

依然考虑以下种转移：

延续连续段。一共有个头尾，所以。
插入连续段。一共有个空。所以。
合并连续段。一共有个空可供合并。所以。

然后依然是的单独转移和赋初始值。最后就是。所以最后答案就是。

树哈希题目

大佬的树哈希教程

UOJ763 【模板】树哈希

题目大意

TL：5s，ML：512MB

这是一道模板题。

给定一棵以点为根的树，你需要输出这棵树中最多能选出多少个互不同构的子树。

两棵有根树、同构当且仅当他们的大小相等，且存在一个顶点排列使得在中是的祖先当且仅当在中是的祖先。

对于所有数据，。

解答

我们构造以每一个点为根的树哈希。因为它和儿子有关系，所以可以构造一个基于儿子的树哈希：

$has_x = C + \sum_{v \in son_x}g(v) \bmod P$

这里我取的（即自然溢出），然后这里定为对的 xor-shift 操作。具体来说：

mt19937_64 rnd(time(0));
ull rng = rnd();
il ull shift(ull x){
    x ^= rng;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 5;
    x ^= rng;
    return x;
}

这样可以对进行映射。

然后就看一共有多少种即可。这个可以通过对数组进行排序 + unique 操作实现。

P5043 【模板】树同构 Exp

题目大意

TL：1s，ML：250MB

树是一种很常见的数据结构。

我们把个点，条边的连通无向图称为树。

若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。

对于两个树和，如果能够把树的所有点重新标号，使得树和树完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。

现在，给你个无根树，请你输出与每个树同构的树的最小编号。

对于的数据，。

解答

树同构可想到树哈希。不过现在因为是无根树，所以这里要求以每一个点为根的树哈希值。我们定为以为根的整棵树的哈希值。那么若使用上到题的哈希方式，可以得出转移式：

$rthas_x = has_x + g(rthas_{fa_x} - has_x)$

然后暴力比较即可。我用的做法。

0711 好题 - CF2118F Swifts and Swaps 3100

题目大意

TL：6s，ML：512MB

给你长度为的数组和以及整数。

这两个数组只包含从到的整数，而两个数组都包含从到的所有整数。

您可以重复对执行以下任一操作：

将数组向左循环移动
交换两个相邻的元素，如果它们的差至少为。

能否将第一个数组转换成第二个数组？

长度为的零索引数组的左循环移动是一个数组，使得中的所有都是数组。

解答

因为差至少为才能交换，所以这里可以看作数会被数挡住，过不了。这就说明所有数和数的相对位置会保持不变。那么我们就可以将所有的数都拿出来分析一下。

那么首先就可以猜想：如果所有的相对位置循环同构，那么就说明答案为 YES，但实际上这是错误的。举一个反例：。和的相对位置分别是，和的相对位置分别是。这两个相等，但是不能通过操作使两个原数组相等。原因就是这个后面跟着的的种类不一样。所以，这个相对位置应该写成和，括号里面的数代表有几个。很明显，它们不能循环同构。

那么可以得出来，两个数循环同构，那么就要必须满足相对位置相等并且种类正确。种类正确指的是递归下去的顺序和个数完全相等。那么关系就可以看成一棵树，两棵树需要同构并且儿子顺序相等。所以这里的树哈希就不能使用平常的基于 set 的树哈希，应该使用基于 vector 的树哈希。

具体实现的话，就可以维护一个桶，代表所有值为和的数的下标集合。可以使用 vector 实现。然后让从小到大维护。假如一个集合为，那么第一个的儿子就是，要得到儿子序列的哈希，这里就不用普通的树哈希，可以使用 map <vector<int>, int> 来维护。

维护到了之后，你就会得到一个包含所有值为的数的哈希值的序列。因为有两个数组，所以也就会有两个这样的序列。最后你就判这两个序列是否循环同构即可。（我都打 maimai 了，只会用 KMP 求是否循环同构，你就让让我吧（（（（）

令同阶，时间复杂度。运行时间 1.5s 足矣。

P12865 [JOI] 冒泡排序机 Mas

题目大意

TL：2s，ML：1GB

JOI 君——一名算法工程师，开发了冒泡排序机。

冒泡排序机操作长为的整数序列。为了让机器能工作，给定作为（）的初值。每当机器上的按钮壹被按下时，机器会按照如下方式修改序列：

对于（按此顺序），若，交换的值。

为了使冒泡排序机更博人眼球，JOI 君决定加入以下功能：

当按钮贰被按下时，给定整数作为输入（须满足），机器会输出的值。

给定整数序列的初值和长度为的冒泡排序机的操作序列，编程计算每一次按钮贰的输出值。

解答

根据冒泡排序的性质，因为每一次冒泡操作其实是将前缀最大值往右边移动，那么相应的，肯定就会有元素被移到左边去。分析一会可以发现，第一次后前个元素就变为了前个元素的前小值（很明显吧，因为第小元素，也就是最大的元素，在第一次冒泡过程中已经被移到了第位或者是被移出去了）。以此类推，第次冒泡操作后，前个元素就变为了前个元素的前小值。

根据这个，并且因为询问可差分，所以我们就可以使用可持久化线段树。这棵树可以用来找任意一段前缀第小值。就可以在查找第小值的时候顺便把前面的和给求了。这样时间复杂度就是正确的，还支持在线。

顺带一提，因为这玩意是动态开点的，并且 ML 1 个 G，所以不用离散化都可以。

CF1083E The Fair Nut and Rectangles 2400

题目大意

TL：2s，ML：250MB

给定个矩形，每个矩形的顶点分别为、、、。对于每个矩形，还给定一个数。你可以选择其中一些矩形，使得所选矩形的并集面积减去这些矩形对应的和最大。

保证不存在嵌套的矩形。

解答

先给这些矩形按照坐标排序，因为不存在嵌套嘛，所以贡献似乎可以拆（我也不知道我在说什么）。

设为考虑前个矩形且强制选择的最大收益。可以获得转移式：

$dp_{i} = \max(dp_{j}+(x_i - x_j)y_i - a_i)\\ dp_{i} = \max(dp_j - x_j\cdot y_i) + x_i\cdot y_i - a_i$

然后发现里面的式子是类的东西，所以可以使用斜率优化来做。

因为不会写那个什么维护凸包的方法，所以只会写李超线段树。并且我在写完调的时候才发现一个东西：李超线段树是可以通过动态开点使得空间复杂度的！这个比较好证明。

随即通过此题。

P5666 [CSP-S] 树的重心 Mas

题目大意

TL：4s，ML：250MB

小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：

一个大小为的树由个结点与条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。
对于一个大小为的树与任意一个树中结点，称是该树的重心当且仅当在树中删去及与它关联的边后，分裂出的所有子树的大小均不超过 （其中是下取整函数）。对于包含至少一个结点的树，它的重心只可能有 1 或 2 个。

课后老师给出了一个大小为的树，树中结点从编号。小简单的课后作业是求出单独删去每条边后，分裂出的两个子树的重心编号和之和。即：

$\sum_{(u,v) \in E} \left( \sum_{1 \leq x \leq n \atop 且 x 号点是 S'_u 的重心} x + \sum_{1 \leq y \leq n \atop 且 y 号点是 S'_v 的重心} y \right)$

上式中，表示树的边集，表示一条连接号点和号点的边。与分别表示树删去边后，号点与号点所在的被分裂出的子树。

小简单觉得作业并不简单，只好向你求助，请你教教他。

本题包含多组测试数据。

对于所有测试点：。保证给出的图是一个树。

解答

君を喪っても　まだ翔べるかが

这道题似乎是最近做的题里面最难的一道题。可以想到我没有做出来。

如果一个点不是一棵树的重心，那么重心就会在这棵树的重儿子的子树内。

如果不删边的话，想快速求整棵树的重心，我们可以预处理倍增数组，即每一个点向其重儿子跳次后的所在位置。同时处理。（父亲、重儿子、子树大小）。当然，这里默认树根为。然后，就可以预处理，求重心了。因为重心最多就俩，所以能往下跳就尽量往下跳，如果不行了，就 check 以下这个点以及它的父亲是否为重心即可。判断某个点是否为重心的方法就是看其重儿子的和的是否超过了。

然后现在，题目要求我们要删边了。那么我们肯定又要做一遍 DFS 了。这次 DFS 的作用是换根。每次 DFS 到一条边的时候，就把一棵树拆为两个部分：以为根的树和以为根的树。对于树，因为新 DFS 到了点，并且把拆了，那么就要重新更新所有和了。可以先更新，然后根据更新其它。。

首先，如果的话，那么就只能割舍重儿子。记点的次重儿子为，这东西也是要预处理的。然后这个时候就替换为，否则就为。然后顺势把更新了。更新了之后，就可以求重心了。注意这个时候要设置和为，等到求完了之后再改回来，然后在下一次 DFS 之前将即可。

注意，所有边遍历完了之后要将和复原。

理解 + 写了这道题花了一下午……要似了……

P5226 [SCOI] 小凸解密码 Mas

题目大意

TL：2s，ML：128MB

小凸得到了一个密码盘，密码盘被等分成个扇形，每个扇形上有一个数字，和一个符号 + 或 * 。密码盘解密的方法如下：

首先，选择一个位置开始，顺时针地将数字和符号分别记在数组和数组中。解密的方法如下：

当时：
- 若为 +，
- 若为 *，

操作完成后，可以得到一个长度为的数组，然后以为起点将数组顺时针写成一个环，解密就完成了，称得到的环为答案环。

现在小凸得到了一份指令表，指令表上有 2 种操作。一种指令是修改操作，即改变原来密码盘上一个位置的数字和符号。另一种指令是询问操作，具体如下：

首先从指令给出的位置开始完成解密，得到答案环。
答案环上会有一些连在一起，将这些连在一起的称为零区间，找出其中距离最远的那个零区间，输出这个距离（零区间和的距离定义为：零区间内所有到距离中的最小值）。

行，依次给出指令。每行第一个整数代表指令类型：

若第一个整数为 1，代表本行对应指令为修改操作，之后依次有两个整数和一个字符，分别代表修改的位置，以及修改后该位置的数字和字符。
若第一个整数为 2，代表本行对应指令位询问操作，之后有一个整数，代表本次操作中解密的开始位置。

密码盘上的位置标号为到。

。

解答

首先修改密码盘是很简单的，一次最多就会修改两个位置。

然后对于查询，那么应该是有这样一个操作，假如说从开始，那么将，然后查询完了之后再赋回去。

那么查询的话，我们可以二分寻找答案：对于距离是合法的，那么肯定要满足在这段区间内（因为原是一个环，越界了就应该能理解从哪里开始），满足有「非 0 数-一些 0-非 0 数」的结构。

一段区间内是否有这个结构可以使用线段树来维护。因为这玩意有可结合性。

P3295 [SCOI] 萌萌哒 Mas

题目大意

TL：1s，ML：125MB

一个长度为的大数，用表示，其中表示数的第位, 是数的最高位。告诉你个限制条件，每个条件表示为四个数，，即两个长度相同的区间，表示子串与完全相同。

比如时，某限制条件，那么，均满足条件，但是，不满足条件，前者数的长度不为，后者第二位与第五位不同。问满足以上所有条件的数有多少个。。

。

解答

暴力做法：对于每一组区间，将所有的使用并查集合并到上（）。假设最后有个集合（即有多少种最终祖先），那么因为每一位只能选个数并且最高位只能选个数，所以答案就是。时间复杂度。时间制限超过。

于是乎，我欲优化。因为离线，而且最重要的一点是，两段区间是相同的。所以我们可以考虑将先合并大区间，然后再把大区间拆成小区间下放到每一个节点上。容易想到在线段树上面做。但是这个是不好做的，而有一种和线段树上做并查集的思想很像的方法就是：将每一个区间按照二进制拆成个长度为的整数次幂个区间，然后先对这些区间合并。

操作完了之后就可以按照区间长度从大到小下放合并的信息了。令为以点为左端点的长度为的区间在层上的并查集里的 father。然后合并就：先令，然后合并组以及组。注意不要越界。

然后最后就统计组一共有多少种最终祖先即可。这玩意随便整都可以过。

优化后时间复杂度。可以过。

树上问题的一些

P1600 [NOIP] 天天爱跑步 Exp

题目大意

TL：2s，ML：512MB

小 C 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含个结点和条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从到的连续正整数。

现在有个玩家，第个玩家的起点为，终点为。每天打卡任务开始时，所有玩家在第秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）

小 C 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点的观察员会选择在第秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第秒也正好到达了结点。小 C 想知道每个观察员会观察到多少人?

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点作为终点的玩家：若他在第秒前到达终点，则在结点的观察员不能观察到该玩家；若他正好在第秒到达终点，则在结点的观察员可以观察到这个玩家。

解答

对于一个玩家从，我们可以认为他是（令为根）。就分成了两部分。然后分开算。

对于一个玩家从开始的，这个玩家很明显是向上跑的。并且观察员只能观察到从其子树的点开始的玩家们。于是乎，假设这个玩家从时间开始向上跑，那么在时刻的时候，玩家到的距离（令为子树内的某点）即为。

要使在时刻时玩家和观察员的距离为，则此时，即。于是问题就变成了：找子树内开始的玩家个数，满足玩家的等于观察员的。初始时所有。这个可以用 DFN 序 + 桶实现。

那么这个时候有人就要说了：欸那么如果这个人跑到之后不是就消失了吗，这玩意没处理啊。那么就可以再派出名玩家，这个玩家从开始跑，开始跑的时间为。这样就可以解决了。

然后对于（不含）也是类似的，将时间逆转，令为玩家到终点的时刻，化一化式子就变成了。然后依然在处派出名玩家使得在处消失即可。时间复杂度为。瓶颈在于预处理 LCA。

P4211 [LNOI] LCA Mas

题目大意

TL：1s，ML：125MB

给出一个个节点的有根树（编号为到，根节点为）。

一个点的深度定义为这个节点到根的距离。

设表示点的深度，表示与的最近公共祖先。

有次询问，每次询问给出，求。

。

解答

这里使用了一个 Trick：可以转化为：将至根的所有点的点权，查找到根的点权和。这个方法适用于求很多个的。

但是对于每一个暴力插入所有在这道题是不现实的，所以可以离线，将即可。这样就可以使用树链剖分 + 线段树来很好地做了。

CF696E …Wait for it… 3000

题目大意

TL：3s，ML：256MB

给定一个个节点的树，有个物品，第个在节点，初始权值为。要求支持两种操作：

对于两个物品，如果它们的权值不同，那么权值更小的物品更好；如果它们的权值相同，那么所在节点编号更小的物品更好。可以发现在这种定义方式下，任意两个物品都能比较出哪个更好。

1 u v k：对于树上的一条简单路径 (,)，删除路径上所有物品中最好的个物品，并将这些物品的编号从最好到最不好的顺序输出；
2 v x：对于一棵子树，将该子树内所有物品权值加。

解答

这道题可以使用树链剖分 + 线段树就可以实现区间加和查找路径上最小值的操作。然后删除最小值就相当于是赋一个最小值为。因为每一次找了之后就把最小值删了，所以最终最多只会找次，时间复杂度是对的。

如果普通地将每一个物品放到该节点上，那么就要在线段树的叶子节点上面维护一个堆，非常的不好写。这里使用先将所有物品按照 dfn 序排序，然后使用 lower_bound 查找修改范围就可以代替堆了。

这个私人 CF 我刚刚写完这道题它就崩了，我到现在都不知道我调出来的是不是对的。现在都 6 点了我还在学校里面，到时候别上晚自习了这个私人 CF 还没好。就只能留校了？？？从教练的角度上来看我现在又没有写完这道题，没办法和教练交差，心里面有一万头【数据删除】在奔腾。

喜报。第二天，即 R7-07-25，中午 12:06 正式过了此题。

CF1823F Random Walk 2600

题目大意

树上从走到，随机游走，求走到每个点的期望次数。。

首先，整个树可以被看作一个拥有条边的有向图。

在一个有向图中，有向边被经过的期望次数只取决于点被经过的期望次数，因为这条边是点出边的一条，出边是等概率选取。

那么我们令为点的出边被经过的期望次数。然后分情况讨论：

边不在路径上。那么你走了就必定要走，所以。
边在路径上。因为一条路径不管你怎么走，不管是简单路径还是复杂路径，走的次数一定比走的次数多。因为你要走到。

所以可以从一步一步推到所有点的答案。

最终答案为。并且特判。

解答

0728 好题 - ARC197E Four Square Tiles 2647

题目大意

TL：2s，ML：1GB

给你三个整数，保证。

求把四个的方形瓷砖铺在的网格上的方案数，瓷砖不能相互覆盖，不能斜着摆放，每个瓷砖必须完整地覆盖个格子。

方形瓷砖之间是完全相同的，也就是说两个摆放方案不同当且仅当存在一个方格在一种方案里被瓷砖覆盖，在另一种方案里没有。

输出答案对取模的结果。

多组数据。第一行一个整数，表示数据组数。

对于每组数据，一行三个整数。

解答

因为，所以可以发现四个正方形应该像特大的四个正方形一样每一个角一个。不存在三个正方形共享相同的或坐标。我们设左上角为正方形 1，右上角为正方形 2，左下角为正方形 3，右下角为正方形 4。~~黄红蓝绿。~~每一个正方形的代表坐标为其左上角的顶点。

令网格长，正方形边长。由此，我们可以列出一车的不等式，使得满足相邻的正方形不重合：

$\begin{aligned} &1\le x_1, \ \ x_1+b\le x_2,\ \ x_2+b-1\le m &(1)\\ &1\le x_3,\ \ x_3+b\le x_4,\ \ x_4+b-1\le m &(2)\\ &1\le y_1,\ \ y_1+b\le y_3,\ \ y_3+b-1\le n &(3)\\ &1\le y_2, \ \ y_2+b\le y_4, \ \ y_4+b-1\le n &(4) \end{aligned}$

解式可得：。于是就相当于是在个格子里面选出两个，方案数为。其它的同理。于是仅考虑相邻的限制下就一共有种。

但是这样的话就会出现正方形 1 和正方形 4 重合的情况。为了不让对角的两个正方形重合，我们算出对角的两个正方形重合的情况种数，不重合的就是总情况数减去重合情况数了。因为正方形 1、4 重合和正方形 2、3 重合的答案相同，所以这里只算正方形 1、4 重合的情况。

那么因为重合了，所以引进式：。联立式可得：。依然是相当于在个里面选个出来，方案数为。的同理。

所以总答案就是。特判答案为的情况即可。