题意 在某些区间必须一样的情况下，可以组成多少个大数。 思路 将询问区间拆分成 若干个小区间，将 区间与区间 合并，最后计算答案时 将区间的信息下放到点上。具体的来讲： 表示左端点为位置 ，长度为 的区间所在集合的根的左端点。最终计算答案时，将所有层的对应端点合并即可，做法是将每层和他的上层合并 即将 与 合并，将 与 合并。 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+5,mod=1e9+7; int n,m,fa[N][18],ans; in...

题意 给你 个点， 条边的无向图，但一条无向边的两个方向的边权不同，求图上最小正环的大小。 分析 考虑 转移式，设 表示走了不超过 条边，从 到 的最大边权(走不通为极小值)。那么转移为： 在我们计算答案时，我们考虑使用倍增。先尝试走了不超过 条边从 走到了 的最小边权和, 从大到小枚举。1.如果没有正环，说明答案大于 ,那么下一步增加 条边。转移时需用到上一次状态，用 记录上一次尝试 的最长路径。2.如果有正环，说明答案小于等于 ，那么下一步尝试 条边。 代码 #include<bits/stdc++.h> #define ll long long c...

题意 给你一个环，有 个区间,区间之间互相不覆盖。求当任意一个区间必须选择时，最少需要多少个区间能够覆盖整个环。 思路 对于一个战士 ，如果选了他，那么下一个战士 一定是所有左端点小于等于 的右端点的战士中最大的一个战士，因为这样子才是是最优的。所以我们只需要预处理加二分找到下一个战士就好了。然后一个一个的找有点慢，所以就用倍增优化一下就好。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e6+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; ...

题意 题目的意思就是每次询问点x，y，要你求其中离它们距离一样的点有多少个。 分析 我们可以先找到这两个点的 ，然后路径的中点肯定是一个解（没有就无解咯）。然后从这个点不经过 这条路径任意一点能到达的点，就是其他解。求法的话，比较两个询问节点的深度 深度相同： 深度不同： 代码 #include<bits/stdc++.h> #define ll long long const int N=1e5+5,INF=0x3f3f3f3f; using namespace std; int head[N],size[N],dep[N],fa[N][15]; int n,cnt,m...

题意 给你一棵有 个节点的树，要求在所有叶子节点到根节点的路径上有一个节点是特殊的（军队）。问如果要封死这棵树，移动距离最大的点移动的最小距离是多少？ 分析 这题挺恼火的，一步一步慢慢来 首先：树上倍增先预处理用存储 节点的第 个祖先的节点编号， 存储 节点到它的第 个祖先的路径长度。在预处理过程中同时也处理出每个节点的深度，用 表示。递推式： 然后：二分答案因为时间越长显然就越容易实现，所以答案具有单调性。 再接着：重点就是check函数了如何判断一个时间限制符不符合条件呢？显然，对于所有军队，我们希望它最后停留的节点深度越小越好，这样可以控制最多的路径。因此我们让所有的军队尽...

题意 PS:（最近好多题题意都好难懂啊QAQ）给你一棵 个节点的树，有 次询问，每个询问给你 三个节点，求树上一个节点使得这三个点到的距离之和最小。每次询问输出这个节点的编号以及路径之和。 分析 考虑每两个节点之间的最短距离就是求这两个点的 ，那么三个点我们可以先两两一组找到 。我们可以发现三个点的 要么是完全一样，要么是有两个（两个相同，一个不同），如果是有两种 那么此时我们要选择不同的那一个这样才能使路径最短，因为可以保证有一条路径不会重复两遍。就比如下面这张图，如果我们的询问是 那么 的 就是 。的 就是 。的 就是 。此时我们的选择就是 ，因为这样可以少走一次 这...

题意 一个无向图可以有重边，下面 个操作，每次在两个点间连接一条有向边，每次连接后整个无向图还剩下多少桥（注意是要考虑之前连了的边，每次回答是在上一次的基础之上） 分析 求出桥来之后缩点，缩点运用并查集实现，每一个点组用父亲节点代表。emm，好像就这样。 PS: 虽说楼上大佬说并查集实现更快，但我还是比 慢啊。我太菜了/kk 代码 #include<bits/stdc++.h> #define ll long long const int N=2e5+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; inline int ...

题意 你有一颗 个节点的有根树(以 号节点为根)，求最少加入多少条边之后使得根节点（即 号节点）到这棵树上任意一点的距离不大于 。 分析 考虑一种贪心，如果一个节点 到根的距离大于 的话，那么我们就从根节点连一条边到 节点的父亲 。 来考虑正确性的证明，一个节点 到根的距离如果大于了 ，那么只会有两种方式连边 直接连向 。 连向他的父亲节点 。 我们分两种情况讨论： 如果 的父亲节点 除了 以外还有别的子节点，那么连向父亲节点 也可以同时覆盖其他儿子。 如果 没有其他儿子，那么连向 可以使得根节点到 的距离也减小，虽然 可能满足距离小于等于 ，但这样一定不...

题意 你有 本书，每本书有一个权值 .你要将这 本书分到 个书架上，要求你分组之后的每组权值之和的按位与的值最大。 思路 位运算啊，按位考虑。贪心的从高位到低位的使得此位值为 。我们就可以枚举最后的答案，从大到小，然后依次 一下。我们设计 方程： 。表示在前 个分为了 组是否成立，最后成立条件就是 。 代码 #include<bits/stdc++.h> #define int long long const int N=1e3+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; int n,k,ans=0; ...

题意 给你一棵 个结点的树, 以 为根。每个结点有点权。有 次操作： 结点权值 ， 的儿子权值 ， 的孙子们 ，以此类推。 询问 的点权； 思路 又是单点查询，看看树状数组吧。区间修改就可以用差分。但是第一个操作有些麻烦，但这和每个节点的深度奇偶有关。所以只需判断一下深度，决定修改的值的正负就好，但是初始值不受影响，故还需用一个数组来存储初始值。 代码 #include<bits/stdc++.h> #define ll long long const int N=2e6+5,INF=0x3f3f3f3f,mod=998244353; using namespace ...

题意 给你一颗以 为根有 个节点的树，每个节点有一个点权。给你 次操作 ，操作有两种类型： 表示将节点 的权值加上 ； 表示求以 为根的子树上所有节点的和（包括 节点）； 分析 我们可以通过 序将一整棵子树上映射到序列中连续的一段上。所以问题就变成了，单点修改，区间和查询。直接用树状数组维护就好了。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e5+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; int n,m,rt,cn...

题意 你有一颗树，每个点有一个颜色，有次操作， 将 节点改为颜色 。询问所有颜色为 的点的生成树大小。 分析 我们可以用序来维护每种颜色的生成树大小。考虑若颜色为的节点只有个、，则其生成树大小就是两个结点在树上的距离，记为。此时，如果加入第个结点，对生成树的贡献能用树上距离算出来： 我们分类讨论：1.如果在、之间生成树的大小为，加号后面的是加入节点的贡献。在分别考虑一下其他几种情况可以归纳出，你加入节点的贡献就是。所以我们可以对相同颜色点的集合按序排序用维护。每次加点或删点就取出左右相邻的个点计算贡献。 代码 #include<bits/stdc++.h> #define ll ...

题意 给你一棵有 个节点以 为根的树，每个节点为 的任意字母。有 次询问，每次询问给出 ，指以 为根的子树内深度为 的所有节点的字母在排列后能否构成一个回文串。 分析 要排列后成为回文串，所以在符合条件的所有节点之中至多只有一种字母的数量为奇数个，其余的字母数量必定均为偶数个。因为回文串的总长如果为偶数，那么所有的字母必定成对（即偶数个）出现；如果长度为奇数，那么只会有一个字母有奇数个，其余均为偶数。 之后就是基本的 的操作了，先将所有的询问以离线的方式存储下来，这样我们就可以一边，一边解决所有的询问，之后统计所有深度,字母的出现次数以便我们的 ，再将轻边子树的信息保留到重链...

题意 你有一棵个节点的二叉树，每个节点有权值，你要选尽量多的点，但是得满足以下限制：对于任意一棵子树，都要满足：如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小。 分析 根的值右子树的最大值左子树的最大值，如果要选择最多的点，那么如果能够处理出根右子树左子树的序，在序列上维护一个最长上升子序列，就能选到最多的点。答案就是序列长度。 代码 #include<bits/stdc++.h> #define int long long const int N=1e6+5,INF=0x3f3f3f3f,mod=9982443...