题意 给出一棵边带权的节点数量为 的树，初始树上所有节点都是白色。有两种操作： ：改变节点x的颜色，即白变黑，黑变白。 ：询问树中最远的两个白色节点的距离，这两个白色节点可以重合 (此时距离为 ) 。分析 无脑上点分树，每个节点维护两个堆 维护子树中最大的长度 ， 自己对父亲的贡献的最大长度。那么答案就是某一个节点 的权值，就是最大值加次大值。那么点分树维护一下就好了。轻微卡常。总复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; #define ll long long int read() { ...

说在前面的 我一看到是点分树，马上就点进来了，很快啊。前置知识：点分治。 约定 表示 的树上路径长度。 引入 给出一颗 个点的树，每个点有一个权值，有两种操作，一种是将某个点的权值修改为 ，另一种是查询距离点 不超过 的点的权值和。 分析 我们考虑暴力，如果将一个操作的复杂度降低到 的话，另一个操作势必会变为 。所以我们的目的还是要平衡复杂度。考虑在每个节点维护两个数据结构。数据结构的下标表示离 为 的权值之和。那么 维护子树的权值和， 维护父亲的子树权值和。 那么查询答案的维护就可以转化为。每次从 跳一下父亲 ，记录 ， 加上 的 的前缀和，再减去 ...

比较有趣(有难度)的数位 。 分析 我们考虑 表示 每一位的积。那么我们先考虑一维的情况，那么我们要求出 最多的一个 。那么这个考虑数位 解决。但是我们发现 还是比较大的。直接表示状态是表示不出来的。但是 就有了一个非常好的性质。 。这样我们发现其实有用的状态非常少，大概 个左右。那么直接用 表示考虑第 位，积 时，没有前导零，是否顶住极限的方案数。这样我们就解答了一维的答案。但是我们是要求前 大的 的答案。这个就是一个套路了，将 排序。那么最优的答案就可以用一个堆维护。 关于堆维护，一：把 拓展到 。二：把 拓展到 和 。本代码选择前者。代码 #i...

前面的话 这篇博客大概是带权二分(wqs 二分，是叫这个名字吧)的入门博客，希望大家点个赞👍。 引入 给你一个序列 。其中 。可以把序列分为 段。定义每一段的价值为 ，现在要求 的总和最小。形式的，我们要最小化 。 分析 我们可以先做一个 的线性 。定义 为 结尾，分了 的最小值。那么转移为 。最后的答案为 。我们再考虑一下优化。 我们可以分析，由于 。所以我们其实要分的段数要越多越好。那么我们得到第一个性质 ，答案是关于段数 的增加而减小的，而且减小值越来越小，因为 ，而我们一定是优先选择 操作的 。所以如果我们定义 。那么 是一个单调下降的，而且...

题意 非常简洁，给你一个有根树。求问 。 分析 我们发现 出现的非常突兀。考虑直接枚举 ，由于每个点对只计算一次。所以只用计算后加入的对前者的贡献。那么一个点的贡献为， 其它子树中权值为 的编号。但是答案为 。这个没有什么结合率和交换率。我们考虑直接拆位。那么令 表示，权值为 ，第 为 的个数。那么一个点的贡献为 。那么现在就是如果统计树上的点对。要么点分治要么树上启发式合并。时间复杂度都是 的。这里不详细展开了。 代码 #include<bits/stdc++.h> using namespace std; #define ll long long int...

写在前面的 这个是个好东西啊，好东西啊（神志不清）。这个方法可以非常简单的求出多元函数的条件最值，而且不需要动脑子，会求导就完了。 引入 求 的最小值。其中 。 如果使用柯西不等式就一步。 。 拉格朗日乘数法的大体步骤为。 令条件函数，和目标函数。 分别对所有变量求出偏导。 令偏导为 ，解方程。 代入目标函数，得出最值。 但是为了讲解拉格朗日乘数法，我们令 那么定义 。那么 。现在令，所有偏导为零。可以解得方程 。最后检验得到 。 证明，不太会。但是可以感性理解一下，如果希望有完整证明的，可以看这个 。大概就是，在两个函数相切时。在切点处，两个函数的梯度向量是平...

说在前面的 和欧拉序都是非常有力的工具，我们应该熟练的运用两者。而且 序也不必局限于树上的 序，其实一般图也有 序，有兴趣的朋友可以参考 算法。 以下的 序，全部指树上的 序， 序即使在树上，仍然不是唯一的。 以下的 ，全部指以 为根，子树的大小。 dfs 序 引入 如何判断 是否有所属关系，也就是 ，多次询问。我们发现我们并不能把每个节点的 记录下来，这使我们不太好查询是否 。 我们可以考虑模拟 的过程，先遍历所有儿子，然后才去遍历其他子树。那么我们发现，如果按照遍历顺序，在第一次遍历到这个节点时，将该节点压入数组。那么节点在新数组的位置叫做这个节点的 ...

分析 设 为字符串中从 到 部分为一整棵树时的方案数。那么考虑子树的划分，那么 ，考虑子树在 处回到根节点。 代码 #include<bits/stdc++.h> using namespace std; #define ll long long const int mod = 1e9,N = 310; char ch[N];int f[N][N],n; int main() { scanf("%s",ch + 1);n = strlen(ch + 1); for(int i = 1;i <= n;i++) f[i][i] = 1; for(...

分析 比较综合的题目，这里说几个关键点。 反转字符串，前缀变成后缀。 二分答案，有单调性。 倍增找父亲，线段树上查找 集合是否有 的元素。 在 树上线段树合并 + 就做完了。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();} while(isdigit(ch)) {x = x * 10 + ch - '0';c...

分析 考虑有动态加字符串的操作，考虑 维护。然后支持一下链上加和单点查询就好了。是挺板子的。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 400000; void change(char *s,int ma) { int len = strlen(s); for(int j = 0;j < len;j++) { ma = (ma * 131ll + j) % len; swap(s[ma],s[j]); } for(in...

分析 我们对于不定根的树形结构的题目，我们首先应该考虑定根考虑。考虑从节点 出发。那么我们得到的最短的欧拉路一定是 ，考虑到每次走完一个子树都必须回到自身，除了最后一次。所以我们在定根之后，就是要选取 。那么我们只要取所有节点作为根的最大值。结合定义可以发现我们就是要求，树上的一条最长路径 。其实也就是直径，找个树的直径的做法就过了。 代码 #include<bits/stdc++.h> using namespace std; #define pi pair<int,int> const int N = 2e5 + 100; vector<pi> ...

说在前面的话 不要被可怕的操作吓跑，战胜恐惧的最好办法，就是面对恐惧，加油，奥利给。但冷静分析一下，好像是道大水题。 分析 分析一下，所有操作其实有用的就是维护一下，集合最大。支持合并。其他的操作都可以开一些标记记录一下。但是合并操作的复杂度如何分析，最值又如何维护。 维护最值 一般维护最值一般考虑 和平衡树。但是只有查询最值和删除集合中一个数的操作。用平衡树就大材小用了，反而会增加常数。关于如何删除集合中一个树的操作，完全可以使用维护两个堆 ，一个添加堆，一个删除堆。那么当查询最值时，如果两个堆顶一样，便都弹出。最后直接返回第一个堆 的堆顶。这个也是一个非常常用的技巧吧，大概是个延迟删除...

本人还没有上紫，打不了 。抱歉 A Array Rearrangment 分析 贪心的考虑 的匹配。把 由小到大排序， 由大到小排序。那么合法方案当 就可以了。时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define ll long log int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f=1;ch ...

分析 不会后缀数组实锤了。考虑求 还可以使用字符串哈希。二分 哈希，时间复杂度也是 。代码也挺短的。 代码 #include<bits/stdc++.h> using namespace std; #define ull unsigned long long const int N = 1e5 + 100,D = 233; ull f[N],g[N],p[N]; int n,m; char s[N],t[N]; ull ask(ull *a,int l,int r) { return a[r] - a[l - 1] * p[r - l + 1]; } int lcp(...