6 月做题记录

2085.

_______
■ ■ ■ ■
      ■
■ ■ ■ ■
■
■ ■ ■ ■
■ ■ ■ ■
■     ■
■     ■
■     ■
■ ■ ■ ■
■ ■ ■ ■
■     ■
■ ■ ■ ■
■     ■
■ ■ ■ ■
■ ■ ■ ■
■
■ ■ ■ ■
      ■
■ ■ ■ ■
———————
D F J K

P11831 [省选联考 2025] 追忆/recall Ult

题目大意

给定一个个点条边的有向图，结点由至编号。第 () 条边从指向，保证。节点 () 有两个权值，保证与均是的排列。

你需要进行次操作。操作有以下三种:

：交换和；
：交换和；
：你需要输出满足以下两个条件的点中的最大值，若不存在满足条件的点则输出：
1. 。
2. 图中存在一条到的有向路径，即存在整数与个结点，满足，，且对于所有，图中存在从指向的有向边。特别地，图中总是存在一条到的有向路径。

注：本题有组测试数据。

对于所有测试点，

，
，，

请注意本题特别的时空限制。

解答

考完了省选后三个月才把这道题补了/ll，还是我太菜了。

DAG 图的可达性问题（所有边的，这玩意我赛时没有发现！），再加上有特别的时空限制，考虑使用 bitset。

先考虑没有修改的情况。

我们可以开个大小为的 bitset。每一个 bitset 代表值为的点，在的限制的范围下，可以为哪些询问做贡献。开的 bitset 肯定是会死的，所以需要将询问分块，每个询问分一块。开的 bitset。

因为暴力区间赋很明显是会死的，所以我们可以考虑先构造差分 bitset，然后再前缀异或变成真 bitset。具体来说，假如第个询问的限制为，那么使 bitset 的位和位均异或等于。然后最后在做前缀异或即可解决限制。

然后是可达性：直接全局跑可达性空间肯定是会炸的，所以这里还是记录一个的 bitset，位为代表点可以在可达性的限制下，为询问做贡献。然后跑一遍拓扑排序即可。

最后就是求的最大值了。还是那句话，如果暴力 checkmax 是会死的，所以这里考虑，因为是 checkmax，所以可以对于点按照的权值从大到小枚举，对于已经被贡献的点，后面就永远不需要、也不能再被贡献了。这里可以新开一个大小为的 bitset，初始全赋、哪个询问被做出贡献就将这一位赋为、当前能被贡献的询问集合为前两个限制再与上这个 bitset 实现。然后使用 _Find_First() 和 _Find_next() 遍历即可。

现在有了修改操作。考虑依然是每个询问分成一组。设在这个询问之前有个修改操作。

这个修改操作会产生最多个关键点。那么我们就让剩下的非关键点先处理之前的操作，然后这个关键点再单独、暴力操作即可。这样关键点暴力操作的时间复杂度也最多是。而又因为，再加上时限，所以可过。

CF1286F Harry The Potter 3100

题目大意

假设有一个包含个元素的数组，现在需要把此数组的每个元素都变为。

可以进行的操作有：

任意选定两个数和，然后把减去。（注意，可以是负数）
任意选定三个数和，然后把减去，把减去。

请输出最少的操作次数。

对于的数据，

解答

我们可以把 2 操作看作从到连了一条边，因为重边肯定不如只连一条边优，并且一个 2 环是可以被替换为操作 1 而不会劣的，所以最终 2 操作连成的边会形成一个森林。

我们定每一棵树最终一定是可以变为全，要不然不如每一个点都执行操作。我们先不考虑，设两个数都是，那么有一种最优的（执行步数）、可行的方案可以这么做：

此时若要合法，那么奇数深度的点权和必须等于偶数深度的点权和。

现在加入限制，那么就有了的可操作空间。我们把奇数深度和偶数深度分为两部分，一次不是在奇数深度就是在偶数深度，所以首先，令奇数深度点权和为，偶数深度点权和为，就要先满足。然后因为每一次要改变奇偶性，所以需要和同奇偶。这样才能合法。

于是我们可以判定一个点集是否可以成为一棵 2 操作树：需存在的子集，令在的补集为，需满足且。这个可以通过枚举判定。枚举时间复杂度。

我们令为点集内最多能有多少棵树。我们就子集 DP：若可以成为一棵操作树，那么。然后枚举子集 DP：。最后答案就是 $全集$ 。

0606T2 / 0610T2 operation

题目大意

给定一个质数和个操作，操作有如下两种：

给定，将修改为。
给定，将修改为。

其中是一个初始为的变量。

你可以以任意顺序执行上面的个操作，得到最终的。你需要求出在中，有多少个数是无论以什么顺序执行操作都是无法得到的。

。

解答

lxs 牛完了（这里指 6 号的题是他搬的），我突然感觉以前的大粪吃的都很香了。

首先，显然的，可以先把第一种操作集合起来，再把第二种操作集合起来，然后跑 bitset。暴力乘法跑 bitset 是不可取的，所以这里使用把乘法转为加法的方式。

那么我们要把乘法转为加法，就要使用到原根。原根定义为的一个整数，使得的阶等于。这里的的阶指的是对于的最小的的。因为如果求到了这个质数的原根的话，所有的数都可以使用的多少次方来表示了，乘法问题就变成了加法问题。求一个质数原根就先把质因数分解，然后从开始枚举，若当前的的所有（为的质因子）都不等于，那么当前的就是这个质数的原根了。

求得原根之后，就相当于是要做一个背包了。因为原来是个环，所以我们要断环为链，将长为的环变为长为的链。每一次 2 操作都是先把原 bitset 向右移，然后和原来的做或操作。

那么因为修改的位置最多只有个，所以可以使用二分哈希来解决。一段区间的哈希值可以使用线段树或者树状数组维护。

P11369 [Ynoi] 弥留之国的爱丽丝 Ult

题目大意

给你个结点和条有向边，点编号为。每条边的颜色是黑色或者白色。一开始所有条边都是黑色的。

你需要进行次操作，有两种操作：

1 k：将第条边的颜色进行反转。

2 u v：询问是否能从只经过黑色的边走到。

满足 , ，，, 。

解答

这是一个有向图，很明显强于 DAG 可达性，所以依然考虑的算法和根号重构。

我们以每个操作重构一次，因为是个操作，所以会有条边会被修改，并且询问可达性的点也只有个。所以我们就可以把所有涉及到的点（包括关键边的顶点和询问点）拿出来并重标号，这些最多也只有个。

之后就是老套路，先抛开关键边求可达性。具体来说就是先抛开关键边缩点，缩点后每一个关键点可以到达哪些关键点，这个用二维数组（一维数组 + 一维 bitset）存。时间复杂度。之后就是只看关键边看每一个关键点可以到达哪些关键点，这个也用二维数组存。这个比较简单，存在的关键边就可以直接把赋为。

对于操作 1 修改：修改即可。对于操作 2 询问的连通性，就可以使用压位 BFS 去求。具体来说，压位 BFS 就是新开一个 bitset ，比较特殊的就在于若，那么就可以到达点。搞一个队列，最开始先把的所有元素赋为，赋为。然后把 push 进队。BFS 的每一次操作就是取出队头，然后目前队头可到达的有效的点集就是 vis &(g[front] | f[front])。然后 bitset 遍历所有的位同时把的所有的这些位改为，并把这些位 push 入队。最后求是否为即可。（注意这里的和已被重编号过）单次询问时间复杂度。

然后找一个可以平衡复杂度的即可。这里的取的是。

Diamond Dust 真好听。

P5311 [Ynoi] 成都七中 Ult

题目大意

给你一棵个节点的树，每个节点有一种颜色，有次查询操作。

查询操作给定参数，需输出：

将树中编号在内的所有节点保留，所在连通块中颜色种类数。

每次查询操作独立。

对于的数据，所有出现过的数在之间，保证每次输入的。

解答

这里介绍一个常用的 Trick：就是一个连通块肯定存在一个属于这个连通块的点，使得所有的属于这个连通块的点都在这个的点分树上的子树内。

所以我们可以对原树进行点分治。因为很明显是这个连通块是在点分树上面最浅的节点，所以我们要对于分治中心，求出的子树内有哪些点，使得到的路径上的和都在里面，然后就可以将其挂在上了，因为很明显这是连通的。

然后现在我们就要求，对于分治中心和一堆挂在上的，如何求出这些的答案。注意因为是的和对二元组有贡献，所以我们可以将其看成矩形加，然后单点求贡献。不过这里因为是分了颜色的，然后一个颜色可能会有很多的矩形，这里我们想实现加矩形并，该如何转化？

我们可以维护其轮廓线，然后扫描线加矩形：

因为一个矩形并肯定是这样式的，设它是个矩形的矩形并，那么它也可以被分割成个矩形使这些矩形的矩形并和原本矩形并相等，并且这些矩形没有交。比较好的分割方法就是按照上面橙色的线的分割方式。维护就让扫描线从右往左扫来维护答案。

注意做完一个询问之后不要再换一个分治中心继续做该询问！因为我们要的分治中心一定能包含这个连通块的所有点，也就是它的深度最浅，所以只有唯一一个！

Potplayer | FLAC | [1/115] Divide et impera! - BlackY.flac

（分治是什么歌（（（（（（（（（

支配集（支配点对）合集

P7880 [Ynoi] rldcot Mas

题目大意

给定一棵个节点的树，树根为，每个点有一个编号，每条边有一个边权。

定义表示一个点到根简单路径上边权的和，表示节点在树上的最近公共祖先。

共组询问，每次询问给出，求对于所有点编号的二元组满足，有多少种不同的。

对于的数据，满足，，所有数值为整数，。

解答

一道支配点对 + 扫描线维护的板子题。

首先把所有点的使用离散化变为颜色，最多也只有可能有种。然后就变成了数颜色问题。

考虑暴力怎么搞。枚举这个，然后枚举这个的所有的点，然后考虑和不在同一个子树的，存在什么样的它管的最宽。

管的最宽就说明在编号上面的差要尽量小。所以你要找的就是在之前已经遍历过的子树上面的所有点的在编号上的前驱和后继。我们可以使用一个 set 来寻找。当前子树遍历完了之后再把当前子树的所有点 insert 进这个 set 里面，就可以保证这个一定是你定的那个点。然后对于一个它管的区域就是（这里令，同理）。

我们维护一个的 vector，代表颜色的掌控范围。然后就把当前这个所管的这个范围 push 进里面。最终颜色的掌控范围就是所有的所有矩形取并。这个套路就是上一道题的套路，直接搬上一道题的做法即可。

但是暴力这个方法很明显是会死的，所以我们使用树上启发式合并（小的并到大的上）就不会有错了！

P8528 [Ynoi] 铃原露露 Ult

题目大意

给定一棵有根树，顶点编号为，对有为的父亲。是的排列。

共次询问，每次询问给出，询问有多少个二元组，满足，且对任意，有在树上的最近公共祖先满足。

以上所有数值为整数。

对于的数据，满足，，。

解答

因为所有操作都是，所以可以直接用替换原本的编号，于是题目就变成了对任意，有在树上的 LCA 满足。

因为还是区间编号连续问题，所以考虑支配对。

合法的点对有多少个不好求，那么我们可以先求出询问里面有多少个不合法的点对。

我们还是钦定一个 LCA ，这样就只能从不同的子树里面找。当时，这一对自然成立。否则当的时候，肯定会造成包含的一些对不合法。具体的话，就是包含但是不包含的不合法。

我们分情况讨论：若，那么的点对全部都是不合法的。的情况同理。那么就可以还是同上一道题的启发式合并，因为我们要求的是给定管的最宽的，所以一定就是的前驱或者是后继。之后就可以把像之前的的矩形全部加上了（把看作轴和轴）。

然后就要求里面有多少个了。这个可以使用从右往左扫的扫描线和线段树来维护就可以了。线段树维护当前区间的最小值、最小值个数和历史的区间的的总和。矩形修改还是把它拆成先再的式就变成区间加了嘛，区间加打 Lazytag 是好打的，然后全局更新历史区间的总和就是也维护一个区间加的 tag，并且这个 tag 如果就不打，并且就不改。这样可以保证结果正确。

最后，还要提醒的就是所有的点对均不合法，所以每一次扫到的时候就要把当前的坐标为的区间，然后扫完了之后就把它减掉即可。

P9062 [Ynoi] Adaptive Hsearch & Lsearch Ult

题目大意

有个点在二维平面上。

有次询问，在第个询问中，给定两个数 ()，你需要找到一对满足，和之间的欧几里得距离最小。

对于的数据，满足 , ，。

解答

这道题是平面最近点对的区间询问版。很显然的，首先可以对右端点进行扫描线，维护左端点的答案。

然后就是这道题最核心的 Trick：考虑对整个平面做一个倍增网格分块，我们这里令底数，那么第一次就是把整个平面划为一个个边长为的正方形、第二次就是划为一个个边长为的正方形、第三次是 ……

我们可以一层一层的维护。假设现在的最小单位是边长为的正方形。

然后从左往右扫每一个点。我们扫到点，先看这个点在哪一个正方形里，然后，把在以这个正方形为中心的的正方形里面的之前的所有点提取出来，这些点和点都可以作为关键点对。

是不是觉得，到后面点越来越多，每个点连的点数会变为级别？放心，这里有一个操作，就是每加一个点到这个正方形里面之前，都要把所有在这个正方形里的，和这个点的距离小于等于当前边长的点全部删除。为什么呢？有两个原因：一是可以将关键点对数减少，这是肯定的嘛，因为把一些以后都不可能参与关键点对的点删了。二是这样为什么是对的，因为假设你删了点，就算后面确确实实存在一个点和的距离比小，也会因为距离，导致它在处理之前层的关键点的时候被算进关键点里面去。这样就可以保证关键点数正确、结果正确。

那么算一下关键点数：对于每一层，每一个正方形里面最多可以存个点。然后每一次一个点连的关键点数就是个。一层就是个关键点对。又因为，所以最多层（），一共就有个关键点对。并且好玩的是，这里是令为底，以这个作底数跑的比较快（因为关键点数毕竟和有关）。

看着比较大，所以不能再使用树状数组来插入了。要使用插入复杂度的数据结构。可以想到有一个修改的数据结构，就是分块。因为你要查最多就查次，的时间复杂度可以接受。这样，这道题就做完了。

需要注意的一点是，这是 Ynoi。为了卡常，这里的给正方形标号的操作不要用 map 或者 umap 状物，自己手写个哈希可以卡常。

回滚莫队合集

P5906 回滚莫队模板 Mas

题目大意

给定一个长度为的序列，次询问一段区间，求区间中相同的数的最远间隔距离。

序列中两个元素的间隔距离指的是两个元素下标差的绝对值。

对于的数据，满足，。

解答

我们发现，加点的时候是好维护的，就是维护当前每一种颜色的坐标的和，然后再跟当前的颜色的取最大值即可。但是删点的时候就不好维护了，因为你的没有办法更新，只能撤销。这种情况下就可以使用回滚莫队算法。

这种莫队又叫不加莫队或者不删莫队。其实就是指在加操作和删操作两个里面有一个好维护，但是另一个不好维护，并且可以撤销，就可以使用。算法的具体流程是这样的：

首先将所有询问按照以下方式排序：
1. 若和不在同一块内，则按照排序。
2. 否则，按照排序。
处理询问，记录当前维护的和上一次访问的块的编号。每个询问会有以下情况：
1. 若当前询问的在同一块，则暴力解决。
2. 否则，当询问的的所在块和上一次访问的块的编号不一样，则撤销之前的影响，并让维护的变为当前询问的所处的块的右端点，变为当前块的右端点。
3. 当维护的小于询问的时，正常维护。
4. 当维护的大于询问的时，先正常维护，记录答案，再一步步撤销的操作使变为当前块的右端点。

这种算法的话，令块长为，最多会大改次，复杂度，每次的小改范围为，小改次，复杂度是，为了平衡复杂度，取差不多，总复杂度就是，也可以根据题目需要适当调大调小块长。

这道题的话，就根据上面的步骤来就可以了。

P8078 秃子酋长 Mas

题目大意

TL：5s，ML：512MB

给一个长为的排列，有次询问，每次询问区间内，排序后相邻的数在原序列中的位置的差的绝对值之和。

对于的数据，满足，，互不相同，，所有数值为整数。

解答

发现每一次修改只会影响前缀、或者后缀，所以使用平常的做法可以做到。但是因为是所以过不了。所以我们需要把那个消掉。

发现加不好加，但是删好删。我们可以预处理每一个位置的前缀和后缀，然后删点的话就修改前缀的和后缀的。然后就变成了只删莫队。处理方法和上面的不删莫队相似，但是在不同块的时候要修改修改，但是时间复杂度相同。

P5386 数字游戏 Ult

题目大意

TL：3s ~ 7s，ML：125MB

给定一个的排列，以及个询问，每个询问包含一个整数四元组，表示查询有多少个整数二元组满足：

；
且对于任意，有。

。

解答

有维但是肯定是不可能直接扫四维。我们可以扫前两维然后维护后两维，也可以扫后两维然后维护前两维。

发现后者比较好做，因为原数组是一个排列，所以你新加一个值就只会有一个位置被激活。你激活了这个位置就可以同时连接左、右两边的连续的被激活的段。我们只需要维护这个位置是不是开头或者结尾，如果是那么这个区间长度是多少。因为一个被激活的块连接的一定是开头或者结尾，所以如果这个位置没有值那就一定没被激活。并且根据这个还可以推出开头的连续段长度和结尾的连续段长度。这个对求整块有效。

求散块就使用一个数组记录这个位置有没有值了。注意合并块的时候要处理前一个块的结尾和后一个块的开头的贡献。

这样就可以实现激活一个点，查询一个点的复杂度了。也正好符合修改次数次。然后维护方法就是回滚莫队的不删莫队维护方法，按照那个方法做即可。

长链剖分合集

众所周知的，树链剖分的方法是相似的，重链剖分就是维护重儿子，长链剖分就是维护长儿子。

长链剖分一般解决的是树上 DP 或是树上计数问题。

长链剖分可以用来维护树上 DP 或是树上计数问题利用了树上的最长链最长的性质，将短儿子合并到长儿子上。然后继承长儿子信息。

P5903 模板树上 K 级祖先 Exp

题目大意

TL：3s，ML：500MB

给定一棵个点的有根树。

有次询问，第次询问给定，要求点的级祖先，答案为。特别地，。

强制在线。

，，。

解答

这道题利用了一个性质，就是任意一个点的级祖先所在的长链的链长都。可以这么想：你跳了层，那就说明这个点到底部的距离最少都会是，那么长链就肯定。

那么该如何利用这个性质呢？我们可以将拆成，使得。先让跳上去层，那么现在所在链的重链长度就了。

然后就可以分情况讨论：现在的再跳层会在链顶之上还是之下？我们求出现在的的和链顶之的差值，和比较。若，则在下面。否则在上面。我们维护链顶向上、向下（向下包含链顶）跳层的结果。这个是可以使用的数组来维护的，因为所有重链的长度之和也就是嘛。

为了好维护这个，这里我们定为的最大的的某个次方。

具体来说，我是这么维护的：在 DFS2 操作的时候同步赋指针。（其实 DFN 序也可作指针。）

void initst(){
    for(int i=2;i<=n;i++) lg[i] = lg[i>>1]+1;
    for(int i=1;i<=n;i++) st[0][i] = fa[i];
    for(int i=1;i<=lg[n];i++){
        for(int j=1;j<=n;j++) st[i][j] = st[i-1][st[i-1][j]];
    }
    for(int i=1;i<=n;i++){
        if(istop[i]){
            int cur = i;
            for(int j=0;j<len[i];j++){
                cur = fa[cur];
                up[dfn[i]+j] = cur;
            }
            cur = i;
            for(int j=0;j<len[i];j++){
                down[dfn[i]+j] = cur;
                cur = son[cur];
            }
        }
    }
}
int que(int u, int k){
    if(k == 0) return u;
    int x = 1<<lg[k];
    int y = k-x;
    u = st[lg[k]][u];
    int diff = dep[u]-dep[top[u]];
    if(diff>=y) return down[dfn[top[u]]+diff-y];
    else return up[dfn[top[u]]+y-diff-1];
}

CF1009F Dominant Indices 2300

题目大意

TL：4.5s，ML：500MB

给定一棵以为根，个节点的树。设为子树中到距离为的节点数。

对于每个点，求一个最小的，使得最大。

。

解答

这道题就是利用了长链剖分维护答案的方式：继承长儿子信息、合并短儿子信息。

我们维护为子树中距离为的点的个数。在这里，为了更好地维护长儿子的信息，我们使用真正的指针来记录：

int *dp[N], val[N], *cur;
// dp：指针数组，val：指向的值域数组，cur：当前指针
void dfs1(int x, int father);
void dfs2(int x, int topx){
    dp[x] = cur, cur ++;
    if(!son[x]) ...
}
void Maisolve(){
    ...
    cur = val; dfs(1, 0), dfs2(1, 1);
    ...
}

然后我们开始遍历点。还是按照 DFS 的方式遍历，先解决儿子，再合并儿子信息。

对于合并长儿子，这道题不需要，因为你向上移动一条边就相当于是平移了指针，这里的正好是平移后的结果。

对于合并短儿子，设现在遍历的短儿子为，我们想把子树的所有信息合并至上，我们就从枚举到 $以为根的最长链的长度$ ，然后将加至上即可。

对于维护答案，我们维护为在点的最大值和答案。初始化肯定是，这里的答案就先继承长儿子的，记得要给重儿子的答案！然后在合并短儿子的时候更新答案即可。

最后，记录答案，返回答案。

粘个代码作为模板 ^=ω=^

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb(x) push_back(x)
typedef pair<int, int> pii;
const int N = 1e6+5;
// mt19937 rnd(time(0));
int *dp[N], val[N], *cur;
int maxdep[N], dep[N], son[N], fa[N];
vector<int> edge[N];
int n, m;
void dfs(int x, int father){
    dep[x] = dep[father] + 1;
    maxdep[x] = dep[x]; fa[x] = father;
    for(int v: edge[x]){
        if(v == father) continue;
        dfs(v, x); maxdep[x] = max(maxdep[x], maxdep[v]);
        if(maxdep[v] > maxdep[son[x]]) son[x] = v;
    }
}
void dfs2(int x, int topx){
    dp[x] = cur, cur ++;
    if(!son[x]) return ;
    dfs2(son[x], son[x]);
    for(int v: edge[x]){
        if(v == fa[x] || v == son[x]) continue;
        dfs2(v, v);
    }
}
int ans[N];
pii merge(pii u, pii v){
    if(v.fi > u.fi) return v;
    else if(v.fi == u.fi && v.se < u.se) return v;
    else return u;
}
pii solve(int x){
    for(int v: edge[x]) if(v != fa[x] && v != son[x]) solve(v);
    dp[x][0] = 1;
    pii res = {1, 0};
    if(son[x]) res = merge(res, solve(son[x]));
    for(int v: edge[x]){
        if(v == fa[x] || v == son[x]) continue;
        for(int j=0;j<=maxdep[v]-dep[v];j++){
            dp[x][j+1] += dp[v][j], res = merge(res, {dp[x][j+1], j+1});
        }
    }
    ans[x] = res.se;
    return {res.fi, res.se+1};
}
void Maisolve(){
    cin>>n;
    for(int i=1;i<n;i++){
        int x, y; cin>>x>>y; edge[x].pb(y), edge[y].pb(x);
    }
    cur = val;
    dfs(1, 0), dfs2(1, 1);
    // for(int i=1;i<=n;i++){
    //     cout<<maxdep[i]<<' '<<dep[i]<<'\n';
    // } 
    solve(1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
}

P5904 HOT-Hotels Mas & 双倍经验弱化版 Exp

题目大意

TL：1s，ML：500MB

给出一棵有个点的树，求有多少组点满足两两之间的距离都相等且两两不同。

与算作同一组。

解答

先考虑弱化版。注意到因为两两之间距离相等且两两不同那么就肯定有一个点，使得分别在的三个子树内且。枚举，时间复杂度。

但是刚刚是弱化版，现在要做长链剖分，就不能枚举了，应该枚举，在处算贡献。

我们设。贡献算在的无非就两种情况：第一种是新加进来的子树里面一个点，前面两个点；第二种就是新加进来的子树里面两个点，前面一个点。

我们先考虑第一种情况：我们令在子树内，在前面。那么这个时候肯定在链上。

那么我们就可以开始设计要维护的东西：我们记为在子树中距离为的点数。记为在子树中，满足：的点对个数。

然后第一种情况就好合并了。枚举然后和计算答案。第二种情况也好合并了，枚举和计算答案。

然后就是维护和。可以首先合并，也就是子树中原本就有的，然后再根据和之前的来计算新的和新的。

注意这里的可能为负数，所以对于，每一条链要开两倍的内存。这里推荐到了长链底然后跳上去开：

void dfs2(int x, int topx){
    f[x] = cnt1;
    cnt1 ++;
    if(!son[x]){
        for(auto cur = x; cur != fa[topx];cur = fa[cur])
            g[cur] = cnt2 ++;
        for(auto cur = x; cur != fa[topx]; cur = fa[cur]) cnt2 ++;
        return ;
    }
    dfs2(son[x], topx);
    ...
}

P7581 路径权值 Mas

题目大意

TL：2s，ML：256MB

给你一棵个点的边带权有根树，根节点为编号为的节点。定义的为子树中深度（指经过边数）比恰好大的所有点。
次询问求一个点的两两之间距离的和。你需要输出这个值的结果。

解答

对于两两之间距离之和，我们可以维护之前的到达当前枚举点的距离之和。然后每次新来一个点，就直接加上新点的到的距离之和和老点的到的距离之和。对于新来的多个点也可以用类似的方法维护，只不过要分别乘以对方有多少个点。

那么这个时候就要维护每一个点的究竟有多少个了。当然也要维护答案。然后将询问离线挂到节点上，每次遍历完了之后就可以求出答案了。

但是这个时候有个问题，就是没有办法继承重儿子的信息，因为这个时候相当于就是让你全局加。（其实这个有办法维护，只是当时我没有想出来）所以我一改前面的维护到的距离之和，改为维护到根的距离之和。然后每一次计算答案的时候就减去一些常数就可以了。

P3899 更为厉害 Exp

题目大意

TL：2s，ML：512MB

设为一棵有根树，我们做如下的定义：

设和为中的两个不同节点。如果是的祖先，那么称“ 比更为厉害”。
设和为中的两个不同节点。如果与在树上的距离不超过某个给定常数，那么称“ 与彼此彼此”。

给定一棵个节点的有根树，节点的编号为到，根节点为号节点。
你需要回答个询问，询问给定两个整数和，问有多少个有序三元组满足：

为中三个不同的点，且为号节点；
和都比更为厉害；
和彼此彼此。这里彼此彼此中的常数为给定的。

。

解答

首先，当为祖先的时候是好算的。现在考虑为儿子的情况。

其实题目就是让我们求所有子树中不超过的的之和。为了更好描述，这里令。

发现维护时前缀和不好求，所以这里直接维护前缀和。然后对于短儿子就合并，现在问题来到了长儿子上。

每次操作肯定要将长儿子及以下所有的点的答案都要加上（因为是记录前缀和）。相当于是个后缀加。但是后缀加明显不好做，所以这里转化为全局加和前缀减（前缀减其实就是只减去至，是的）。然后全局加问题的话，我们记录一个 lazytag。每次合并儿子的时候也同时合并 lazytag。然后最后的答案就是原本的答案加上当前根的 lazytag 就是了。

具体流程如下：

void solve(int x){
    for(int v: edge[x]){
        if(v != fa[x] && v != son[x]) solve(v);
    }
    if(son[x]) solve(son[x]), tag[x] += tag[son[x]] + siz[son[x]] - 1;
    for(int v: edge[x]){
        if(v == fa[x] || v == son[x]) continue;
        tag[x] += tag[v] + siz[v] - 1;
        int lenv = maxdep[v] - dep[v];
        for(int i=0;i<=lenv;i++){
            dp[x][i+1] += dp[v][i];
        }
    }
    dp[x][0] = -tag[x];
    int len = maxdep[x] - dep[x];
    for(auto [k, idx]: que[x]){
        ans[idx] += dp[x][min(k, len)] + tag[x];
    }
}

~~当然我写 Maisolve 就是为了避免这种 solve 就是了~~

P10641 攻略 Exp

题目大意

TL：1s，ML：512MB

给定一个有个结点的树，树有点权且点权为正整数。现选取条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。

对于所有数据，保证，。

解答

考虑最基本的贪心算法。就是首先选值最大的那一条链，然后把那条链删了，然后再选删了之后值最大的那一条链，然后再把那条链删了……

这个东西本质上是和树链剖分相同的，所以我们这里做个“值域链剖分”，重儿子的值更大。然后我们选出前大的链，然后计算这些链的点权总和即可。

*CF958B2 Maximum Control (Medium) 2200

题目大意

TL：3s，ML：250MB

给你一棵由个点组成的树，对于一个点集，它所占领的点为：

点集的所有点
对于任意，到路径上的点。

现在问当点集的大小为到时，占领的点的数量最大是多少？

解答

个点的答案就是个点，两个点的答案就是直径。

个点的时候，就是直径加上旁边选一些链的最大值了。选链的最优的节点肯定是叶子节点。所以又变成和上一道题一样的做法了。

CF504E Misha and LCP on Tree 3000

题目大意

TL：8s，ML：500MB

给定一棵个节点的树，每个节点有一个小写字母。

有组询问，每组询问为求树上和组成的字符串的最长公共前缀。

。

解答

如果不是在树上的话，肯定会想到二分哈希。而在树上的话，就只能想到二分哈希了，因为其它方法都行不通。

假设我们要求树上的哈希值，那么就会分成几种情况：从下到上、从上到下。

从上到下的哈希值是好求的。我们维护，然后求即可。

从下到上的哈希值比较难搞。我们维护。然后求。这个除法最开始我觉得不好求，因为我用的是自然溢出哈希。所以我就把反哈希值除改成了正哈希值乘。具体来说我维护了一个，代表这个哈希值是正常的哈希值乘了个。然后比较的时候就分类讨论。结果最后发现这个 Codeforces 是非常及其特别超级私募没有素质的，它不仅卡自然溢出，还卡单模哈希。这导致了我之前的分讨全部白费。只能老老实实写多模哈希的逆元，然后最后给他除过去。（当然这里没有写，是因为我在意识到 CF 卡哈希时，之前的代码已经构成了一座屎山）

这里我们要求路径上的前个字符串所组成的哈希值。那么就会分几种情况讨论（这里令）：

在的上面，那么直接求相对于的第个儿子，也就是求的第个祖先，然后求这条链的哈希值。
在的下面，那么直接求跳级祖先的这条链的哈希值。
否则记，若的级祖先已然超过了，那么再算上相对于的某个儿子，然后合并两条链的哈希。否则就直接求的级祖先的链的哈希值即可。

最后，因为是二分哈希嘛，所以就正常处理询问、二分比较就完了。

顺带一提，最开始我设的是八位质数，后面意识到有多模哈希的时候我就一个自然溢出，另外一个使用十一位质数，后面调试的时候发现爆 long long 了，所以最后把改成了九位质数，开 C++20 就过了。

*P9399 人生如树 Mas

题目大意

TL：2s，ML：512MB

给定一棵个节点的树，节点上有权值。有次询问。

设当前树上的节点数量为。

输入四个整数。令的简单路径上顺次组成的数组为，的简单路径上顺次组成的数组为。求出。保证。
输入两个整数。代表新建一个点权为的节点，编号为，建立一条的无向边，其中。显然，此后。

对于两个数组，设它们的相似度表示最大的满足且对于所有 ，都有。其中表示数组的长度。特殊地，若不存在这样的，则。

，，。

解答

步骤和上一道题一样。只需要再记录一个序列的前缀哈希值，然后将其加入比较即可。

这道题比较好的一点就是这道题不卡单模哈希。私募 Codeforces。

P6961 Journey from… Mas

题目大意

TL：3s，ML：512MB

给定一个无向图（其中点和点一定连通），其中有个点、条边，每条边有一条边权。你可以选择从到的一条简单路径。给定一个常数，当总边数时，付的钱是所有边的边权之和；当总边数时，付的钱就是边权前大的边的边权之和。求从点到点所付的钱的最小值。

。

解答

我们可以首先求从到的最短路作为基础答案。

然后我们枚举每一条边，然后钦定这一条边作为第大的边，然后建一个新图，每一条边的边权是，其中为原边权，为第大的边的边权，然后再求到的最短路，令答案为，那么此时的答案就是。最后的答案就是所有的钦定边的答案和原最短路答案的最小值。

为什么这样做是对的呢？我们分讨一下：

当此时真的是第大边边权，那么正好。
当此时大于第大边边权，那么后面就会在部分使答案变大，即不优。
当此时小于第大边边权，那么就会在算的时候使答案变大。

所以这样做是对的。视同阶，那么时间复杂度就为。可以过之。

P8511 [Ynoi] TEST_68 Mas

题目大意

TL：3s，ML：512MB

给定一棵个节点的树，第个点有一个权值。

对每个点，其的答案为其所在子树外的所有点中，选两个可以相同的点，异或的最大值，如果选不出两个点，则认为的答案是。

求出所有的答案。

对于的数据，满足，。

解答

遇到这个两个元素异或的，可以考虑使用 0-1 Trie。首先我们可以求出全局选哪两个点的答案最大。可以边插边查，这个是的。我们定异或出最大答案的两个索引分别是。

然后我们可以发现，当不属于的任一祖先时，答案就是之前算出来的全局答案。对于剩下的点，就只能是到根的链和到根的链这两条链了。

对于一条链求答案，我们从上往下跳，跳到的时候，就先查，然后把这个点插进去，然后再把所有属于的子树但是不属于的下一个元素的子树的点插进去。这样，求得一条链的答案的时间复杂度就是。因为一共有两条链，所以这道题做完了。

P6072 Path Mas

题目大意

TL：1s~3.5s，ML：244.14MB

给定一棵个点的无根树，边有边权。

令分别表示树上之间的简单路径上的所有点的集合和所有边的集合，特别地，当时，，。

再令边集的权值为中所有边的权值的 异或和，当时，。

现在，要你求出

$\max_{1\le x,y,u,v \le n,V(x,y)\cap V(u,v) = \varnothing}(f(E(x,y)) + f(E(u,v)))$

通俗的讲，你要选择两条简单路径，满足没有重合的点，且边权异或和之和最大。

对于的数据，，，。

解答

首先，一条路径的异或和，很明显可以被转化为，其中代表点到根的所有边的异或和。

这样，题面就可以转化为：给定原树，你需要对于每一个点找出：

在子树内、异或和最大的两个点的异或和
不在子树内、异或和最大的两个点的异或和

第二个就是上一道题求的。第一个的话可以使用 Trie + 树上启发式合并做。因为所以随便过（其实目前我也不知道树上启发式合并的复杂度……）。

不过，要注意必须要选两条路径，也就是个点出来。所以不能取节点 1 的答案（这里我是以 1 为根）。然后对其他答案取即可。

P4931 情侣？给我烧了！ Ult / *P4921 弱化版 Mas

题目大意

TL：1s，ML：500MB

有对情侣来到电影院观看电影。在电影院，恰好留有排座位，每排包含个座位，共个座位。

现在，每个人将会随机坐在某一个位置上，且恰好将这个座位坐满。

如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。

你的任务是求出共有多少种不同的就坐方案满足恰好有对情侣是和睦的。

两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有种不同的就坐方案。

由于结果可能较大，因此输出对取模的结果。

输入包含组数据。

对于的数据，满足。

解答

我们可以将这个问题分成两个部分：先把对情侣匹配了，剩下的对一对都不能匹配。

那么就先解决在排座位中匹配对的方案数。首先选位置：无序的位置一共就是种。然后选情侣：无序情侣也一共有种。然后一一匹配，就要乘上，最后情侣内部可以交换，就再乘上。所以一共就是种。

然后解决剩下排座位一排都不能匹配的问题。我们定为使排座位每一排都不能匹配上的方案数。

那么可以使用递推的方式：首先人会和人匹配。那么我们定人会坐在某个位置，一共有种情况，因为不能让人匹配上，所以会让人来匹配人，此时共有种情况。我们令匹配人的人编号为，的情侣为。

现在我们分类讨论：若最终会和匹配，那么我们枚举的位置，共种。然后自然会坐到他旁边，然后就变成了的子问题了。而若最终不会和匹配的话，那么就相当于是加上了不能和匹配的限制，让它们成为一对新的情侣，就变成了的子问题了。所以这种的递推式就是。初始值。

然后就可以预处理所有要用到的信息，每一次求答案了。

线性基专题

虽然就是因为前几天有一道 T1 考线性基被爆了才去学的来着……

P4570 元素 Exp

题目大意

TL：1s，ML：125MB

给定个矿石，每一个矿石有元素序号和魔力值两个信息，你可以取出若干个矿石（每种矿石可以取若干个），使它们的元素序号的异或和不为，所对应的权值为每一种取出来的矿石的魔力值之和。求权值最大值。

，，。

解答

考虑异或不为的限制。因为注意到，在线性基中，加入你插进来的一个数可以被线性基内的数表示，那么就说明有异或和为的了，就插不进去了。所以现在要找到一个比较好的方法，使得插进线性基里面的权值和最大。

我们可以发现，假如你现在线性基插不进去，那么你可以删掉线性基里面一个特定的元素使得这个东西可以插进去。并且要求魔力值最大的话，那么就按魔力值从小到大插，如果这个插不进去，那么就找到一个能替换的并且值魔力值最小的替换掉。这种方法其实和按魔力值从大到小插不替换是等价的。然后这道题就做完了。

P3857 彩灯 Exp

题目大意

TL：1s，ML：125MB

Peter 女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排个独立的灯泡构成的，并且有个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有个样式。由于技术上的问题，Peter 设计的每个开关控制的彩灯没有什么规律，当一个开关被按下的时候，它会把所有它控制的彩灯改变状态（即亮变成不亮，不亮变成亮）。假如告诉你他设计的每个开关所控制的彩灯范围，你能否帮他计算出这些彩灯有多少种样式可以展示给他的女朋友？

注：开始时所有彩灯都是不亮的状态。

输出答案的结果。

对于的数据，和不超过。

解答

很明显的，我们可以将每一个开关控制的范围那个字符串看成一个位的二进数。然后初始不亮就是二进制表示下的个。然后就问有最终异或出来的结果有多少种。

我们可以将每一个线性基里的数看作将第位和后面的某些位反转。这样，就可以比较容易的证明线性基里每一种选数的集合所异或出来的结果是不同的，所以一共就有种异或结果。

P4301 新 Nim 游戏 Exp

题目大意

TL：1s，ML：125MB

传统的 Nim 游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。

本题的游戏稍微有些不同：在第一个回合中，双方可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。从第二个回合（又轮到第一个游戏者）开始，规则和 Nim 游戏一样。

如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。如果不能取胜输出。

对于全部的测试点，保证，。

解答

众所周知的，传统的 Nim 游戏的必输条件是异或和为，必胜条件是异或和不为，因为异或和为要不就是没有后继状态了，要不就是只能转为异或和不为；所以只能是必输状态。必胜状态亦然。所以我们要选若干个整堆火柴使得第二个玩家怎么取异或和都不为。那么就是让第一个玩家取得不能插入线性基里的数，并且安排插入顺序使得这些数之和最小。

那么就可以类比第一道题的思路，从大到小插，然后把不能插的数取出，这样的和最小。（但其实我也不会证明）

P4151 最小 XOR 和路径 Mas / *CF845G Shortest Path Problem? 2300 Double exp

题目大意

TL：1s，ML：500MB

考虑一个边权为非负整数的无向连通图，节点编号为到，有条边。试求出一条从号节点到号节点的路径，使得路径上经过的边的权值的 XOR 和（即异或和）最大。

路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 XOR 和时也要被计算相应多的次数，具体见样例。

对于的数据，，，。有重边、自环。

解答

我们可以先找出来一条从的主路径。然后定这条路径是必须走的。然后这个图就会可能有很多个环。发现一个环是可以被计入异或和而没有代价的是因为你可以先从走到这个环的开头，然后绕环一圈，然后再走回点。可以发现从到环头的这条路径被两次异或抵消了。

所以就变成了：一条主路径权值，这个必须要算。我们定其为。然后把剩下的环的权值都搞出来，现在要求在环的权值里面选若干个，使其和的异或和最大。很容易想到使用线性基来维护环的权值，然后最后用来查最大值。

P3733 八纵八横 Mas

题目大意

TL：1s，ML：125MB

有一个国家。这国家里面有个城市。初始时有条高速公路，每一条高速公路有一个非负权值。一条高速公路连接两个城市。初始时图连通。

现在要建一些高铁。每一条高铁连接两个城市并且每一条高铁也有一个非负权值。我们定答案为从开始，最后走到的路径上的权值的异或和的最大值。

给定个操作，每次操作会有以下情况：

Add x y z：在城市中建一条权值为的高铁。如果这是第个 Add 操作，那么就把这条高铁命名为号高铁。
Cancel k：拆除号高铁。保证此时号高铁存在。
Change k z：将号高铁的权值修改为。

现在需要求没有操作之前的答案和每一次操作后的答案。共行。

，，，。两个城市之间可能有多条高速公路或高铁，高速公路或高铁的两端可能是同一个城市（即：有重边，有自环）。

解答

类比上一道题的思路，从到的路径权值其实就是，所以只需要求所有环中选取任意个的异或最大值即可。

初始时，不加边，那么就直接像上一道题一样求。新建高铁也是好做的，但是现在多了拆除高铁和修改权值两个操作。这两个操作无法使用普通的线性基维护，所以可以使用可删除线性基。但是我不会这个科技，所以换个思路，线性基不能删除但是可以撤销！所以可以使用时间轴的线段树分治来维护这个线性基即可。因为高速公路永不拆除并且连通，所以可以直接使用 dist 数组维护环的权值。

注意命名高铁的时候注意是第个 Add 操作而不是第个输入！

P3265 装备购买 Mas

题目大意

TL：1s，ML：125MB

脸哥最近在玩一款神奇的游戏，这个游戏里有件装备，每件装备有个属性，用向量表示 ()，每个装备需要花费，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。

严格的定义是，如果脸哥买了这件装备，那么对于任意待决定的，不存在使得
（均是实数），那么脸哥就会买，否则对脸哥就是无用的了，自然不必购买。

举个例子，，就有，那么如果脸哥买了和就不会再买了。

求能够购买的最多装备数量，以及在购买最多数量的装备的情况下的最小花费。

对于的数据，。

解答

这道题才是真正的线性基模板。之前的线性基都是异或线性基。

这道题的题意就是选出尽量多的向量使这些向量线性无关并且使价值最小。

类比之前构造异或线性基的方法，我们可以使用高斯消元法来构造线性基。

还是记录一个大小为的数组。然后插入就从开始遍历。如果要插入的向量在这个地方没有值，那么跳过。如果有值，那么就看这个地方是否已经被另一个向量占领了。如果是，那么就要把这个向量的这一维消去。同时为了保持线性基的性质，所以要同比例消去，然后继续遍历。否则就可以直接插入然后退出了。

bool insert(Vector w){
    for(int i=1;i<=m;i++){
        if(abs(w.p[i]) < eps){ w.p[i] = 0; continue; }
        else if(hav[i]){
            double k = w.p[i] / val[i].p[i];
            for(int j=i;j<=m;j++){
                w.p[j] -= k * val[i].p[j];
            }
        }else{
            val[i] = w; hav[i] = 1;
            return true;
        }
    }
    return false;
}

然后是在最多元素的情况下的最小花费，那么就可以使用贪心，按照权值从小到大插入，最后提取出所有在线性基内的元素的元素个数和权值和即可。

P5556 圣剑护符 Mas

题目大意

TL：1s，ML：500MB

给定一个树形结构，有个点。每一个点上有一个权值。现在要做个操作。每一个操作有以下两种：

Update x y z：把简单路径路径上的所有点的权值都异或上。
Query x y：判断对于编号分别为的点间的简单路径上的所有点的集合，是否存在两个不相等的子集（可以是空集），使得两个子集的属性值相同。一个集合的属性值为这个集合中所有元素的权值的异或和。

。

解答

第一道场切的线性基 =ω=

思路比较简单。因为发现查询操作可以化为把的所有点搬到线性基上，看是否有点插不进去。因为，所以线性基内最多个元素，所以当时就像的是路径间元素直接输出 YES，否则就暴力插。这样的复杂度是能接受的。

现在就要解决树上路径异或问题。这个可以使用重剖解决。并且重剖单点查询，这样就可以使查询复杂度，修改复杂度因为条链，线段树维护，所以复杂度也是。可以通过此题。

P3292 幸运数字 Mas

题目大意

TL：2s ~ 6s，ML：2

给定一棵个点的树，每一个点有一个权值。有个询问。每次询问，可以从路径上的点的集合任意选元素，求这些元素的最大的异或和。

。

解答

线性基有一个比较重要的性质：就是线性基可以合并！那么就可以将其视为具有和 RMQ 问题类似性质的问题（类似树上 RMQ）。于是就可以使用倍增做。因为线性基合并，那么每次取一条链的线性基就可以。于是求一条路径上的线性基就是了。预处理复杂度，查询。

CF1120D Power Tree Mas

题目大意

TL：2s，ML：250MB

给定一棵个点的有根树，为根。定义为叶子当且仅当它不是根且度数为 1。

你可以选择花费的代价控制点。当一个点被控制时你可以选择给它的子树内的叶子的点权都加上一个自己选定的值。你需要控制若干个点，使得花费的代价尽量少，且无论怎样规定所有叶子的初始点权，都可以通过调整你选择的点的值来让所有叶子的点权变为。

你需要输出最小代价和并构造所有最优选取方案的并集。

。

解答

首先，区间加或者减一个数可以看作差分数组上两个点加减一个数。因为一个点是掌管着一个区间的叶子节点的加、减的（这很明显，叶子节点可以通过 DFN 序标号），一个点可以看作从到连一条权值为的边，现在要使一个差分数组全部变成，那么就需要这个图连通，于是求这个图的最小生成树即可。

0630T1 - P7294 Minimum Cost Path P Ult

题目大意

TL：1s，ML：250MB

Farmer John 的牧草地可以看作是一个（）的正方形方格组成的二维方阵（想象一个巨大的棋盘）。对于，从上往下第行、从左往右第列的方格记为。此外，对于每一个，第列拥有一个代价（）。

Bessie 从方格出发。如果她现在位于方格，则她可以执行以下操作之一：

如果，Bessie 可以以的代价移动到下一列（增加一）。
如果，Bessie 可以以的代价移动到下一行（增加一）。

给定（）个独立的询问，每个询问给定（），计算 Bessie 从移动到的最小总代价。

解答

我们可以使用扫描线，维护当从左往右扫的时候，对于每一个的答案。

考虑最开始的最暴力的 DP 做法嘛。因为 DP 式子可以写为，所以我们考虑里面的两个式子：就相当于是，先把所有点的点权赋为里面的第二个式子，然后把所有的点的点权的值按照从小到大改为。又因为可以证明这个是随着的增大而不降的，所以修改的一定是一个后缀。

所以我们维护一个栈，栈里面存按照区间的下标前后关系存区间的左端点、右端点、最开始被修改的时间、、和这个区间的在时刻的两两之间的差值。这样每一个区间的每一个的值就可以被算出。每次就把实时最小差值的区间弹出。这时最后一个区间可能也有一部分要被弹出，所以我们要二分出要弹出的这个点，然后修改最后一个区间的右端点，然后插入新区间，值也可以算出。这样每次维护的时间复杂度就是。总维护的时间复杂度就是。（栈的总加入、弹出的区间个数为个。）

然后查询的话，就二分找到对应的区间，然后求出值即可。