给定一棵无根树，在树上选 $k$ 条路径，它们的并构成一个包含 $u$ 的连通块，要使连通块中包含的边的权值和最大。

一道纯粹的性质题。

首先，一棵树能够被 $k$ 条链覆盖，当且仅当它有不超过 $2k$ 个叶子。

这里必要性是显然的，至于充分性，构造任意一种所有叶子都被覆盖，每条边长度至少为 $1$ 的方案，如果树没有被完全覆盖，找出任意一条极长的没有一条边被覆盖的非空路径 $p$。显然 $p$ 的端点 $u,v$ 不为叶子，因为端点为叶子，意味着路径 $p$ 包含了叶子的唯一出边；而方案中所有叶子都被覆盖，意味着叶子的唯一连边也被覆盖，这与 $p$ 的要求矛盾。既然 $u,v$ 不为叶子，而 $p$ 极长，那么 $u,v$ 一定分别存在于两条覆盖路径 $s\to t,x\to y$ 上。此时我们调整方案，将这两条路径换成 $s\to x,t\to y$，原来被覆盖的所有边仍然被覆盖，而为被覆盖的路径 $p$ 被覆盖。因此我们不断进行这样的调整，这个过程一定会在有限步内结束。

其次，选择 $k$ 条链，构成的包含边权和最大的子图，一定是连通的。一个不连通的方案，通过上述调整方法可以使其变得连通，并且更优。也即我们只需要保证我们能够考虑到最优方案，并不需要注意我们是否考虑到了不连通的选链方案。

---

不难发现，包含边权和最大的连通块至少包含带权直径的端点中的一个，调整法易得。

鉴于正权树的带权直径的两个端点一定是叶子，问题形式变为，分别在以两个端点为根的树中，选择 $2k-1$ 个叶子，要求它们到根的路径的并形成的连通块包含 $u$，求连通块内边权和最大值。

抛开连通块包含 $u$ 的条件，进行一个简单的贪心——长链剖分（注意这里是划分边集，可能有出现在多个链中，而非像大多数树链剖分一样划分点集），然后选择最长的 $2k-1$ 条链构成该连通块。它的正确性也很显然，最优解必然可以表示为几个长链的并，否则一定存在某个长链，该方案只包含了这个长链的某个真子集，那么此时将这个长链并入该方案，不会使其产生新的叶子，却会使该方案的答案增加。每个长链恰含有一个叶子，也即我们能够选择最多 $2k-1$ 条长链。所以选择长度最长的 $2k-1$ 条长链一定不劣。

如果这样构造出来的方案不包含 $u$ 呢？我们需要做出一些调整。

第一种调整方法是只选长度最长的 $2k-2$ 条链，外加一条根到 $u$，再到 $u$ 子树内深度最大点的路径。

第二种调整方法是将 $u$ 的最近的在连通块内的祖先 $f$，不选 $f$ 以及它所在的长链中 $f$ 以下的部分，而是选择 $f$ 到 $u$，再到 $u$ 子树内深度最大点的路径。

首先将原题题意转化为，构造排列 $p$，要求在有根树上如果 $u$ 是 $v$ 的父亲，则 $p_u<p_v$。

最大化 $\sum p_iw_i$ 的值。

从极端情况入手，考察树上权值最小的非根点 $u$，不难发现它在排列上紧随其父亲 $f$ 之后（即 $p_u=p_f+1$）一定不劣。于是我们便可以将 $f$ 和 $u$ 作为一个连续段考察。具体来说是将两个权值放进一个节点中，新节点的儿子为 $u$ 的所有儿子和 $f$ 除了 $u$ 之外的儿子，新节点的父亲为 $f$ 的父亲。

那么我们不免想到，经过第一次合并后整个序列是否能够按照类似的方式继续贪心地合并呢？

我们考察一个平均权值最小的连续段 $u_1,u_2,\cdots,u_s$，证明它在排列上紧随其父亲之后一定不劣。

考虑一种它没有紧随其父亲之后的方案，假设它前面一个连续段为 $v_1,v_2,\cdots,v_r$，$v$ 前面排列里有 $p$ 个数，我们交换 $u,v$ 所带来的答案增量为

$$\displaylines{\begin{aligned} \Delta&=\left(\sum_{i=1}^s(p+i)u_i+\sum_{i=1}^r(p+i+s)v_i\right)-\left(\sum_{i=1}^r(p+i)v_i+\sum_{i=1}^s(p+i+r)u_i\right)\\ &=s\sum_{i=1}^rv_i-r\sum_{i=1}^su_i\\ &=rs\left(\frac{\sum_{i=1}^rv_i}r-\frac{\sum_{i=1}^su_i}s\right)\\ &\ge0 \end{aligned} }$$

由此可得，如果 $u$ 前面不紧邻父亲，那么交换它与它前面的连续段之后一定不劣。

此时做法已经呼之欲出——用数据结构维护所有可合并连续段，每次找到平均权值最小的，将它和父亲合并，同时维护连续段内贡献。

转化题意：给定一个图，每条边有边权 $(a,b)$，多次给定 $u,v,x,y$，询问 $u$ 到 $v$ 中是否存在一条路径 $p_0,p_1,\cdots,p_k$，使得 $\max_{i=0}^na_{p_i}=x$ 且 $\max_{i=0}^nb_{p_i}=y$。

首先抛开相等的限制，单是考虑所有所有 $a_i\le x,b_i\le y$ 的边 $i$ 是否能够连接 $u,v$。这是一个类似二维数点的问题，但是它不能将边划分为两个集合，分别求得答案后相加，也即答案在元素集合维不具有可加性。于是无法 CDQ 分治。

考虑分块用并查集维护连通性。边按照 $a$ 排序，分块，并依次处理。将询问按照 $a$ 分到不同的块中，发现所在块之前的所有块内的边 $a$ 限制一定满足，之后的所有块内的边 $a$ 限制一定不满足，所在块内的边可以暴力处理。

先考虑每个块处理时，它前面的所有块。这些块只需要考虑 $b$ 限制。故维护这些块按照 $b$ 排序的结果，每处理完一块就归并进去。块内询问也按照 $b$ 排序，双指针扫，即可线性将每个块之前的所有块中合法的边加入并查集。

对于每个询问，处理完前面所有块之后，加入本块中满足条件的所有边并判别连通性。注意到这些块内边并不具有单调性，在前面询问涉及到的边不一定在后面询问中出现过，所以需要在处理完后撤回（实际上这就是回滚莫队）。

想起来我们起初将“路径上权值最大值等于 $x$”的限制弱化为“路径上所有边权值不超过 $x$”，这里的处理也很简单，并查集维护连通性的同时分别维护连通块内所有边 $a,b$ 的最大值。注意在往并查集中加边时，无论边的两个端点是否连通，都需要更新最大值；只有两个端点不连通时，才更改连通性相关的信息。

如果没有换根，子树询问转化为区间询问。同 [SNOI2017] 一个简单的询问，由于询问在序列维上具有加性，将区间询问变为四个前缀询问后容斥。前缀询问使用莫队解决。

考虑到换根+子树的经典做法，分类讨论：

• 如果 $u$ 为根，子树即整棵树。
• 如果 $u$ 不在 $0$ 到根的链上，子树不变。
• 否则 $u$ 的子树为整棵树除去 $u$ 包含根的那颗儿子子树。

第三种情况，要么把询问拆成前缀加后缀的形式，要么拆成整个序列减去某个区间的形式。

第一种方法会将一个区间询问拆成九个前缀询问，会被卡常；第二种方法可以一通推式子，对整棵树相关的答案进行预处理。这样就仍能在四个询问内解决。

图中存在一条起点、中转点、终点之间的点不重路径，当且仅当在该图的广义圆方树上，中转点所在的某一个点双对应的方点在起点和终点对应的圆点之间的路径上。

那么给广义圆方树上所有方点赋权为该点代表的点双连通分量大小，圆点赋权为 $-1$，这样选定起点、终点后，中转点的方案数等于起点、终点在广义圆方树上对应的点之间的路径上所有点的点权和。路径上两个方点之间的原点的 $-1$ 可以减去两个点双中该圆点的重复贡献；路径的起点和终点的两个 $-1$ 可以减去中转点和起点、终点重合的情况。

我们考察 Kruskal 算法的过程：

将所有边按照边权分为一些等价类，按照边权从小到大，依次将等价类中所有边在保证无环的基础上尽量加到森林中，直到构成一棵树。

注意到等价类内部是无序的，那么同一等价类中的不同选法就导致了最小生成树的不同树形。

那么由此看出，在加入所有边权小于 $w$ 的等价类之后，等价类中不存在加入森林后能够使两棵树连接在一起，改变其连通性的边。此时的树的连通情况和将这些等价类中的所有边全部加入的图是一样的，也即，不论等价类内部如何选边，此时树的连通情况是确定的。

这也就是说，不同等价类之间选边方案是独立的。所以我们分别考虑每个等价类的选边方案。

加入所有边权小于 $w$ 的等价类之后，将已经形成的连通块缩点，边权等于 $w$ 的等价类的选边方案数可以运用矩阵树定理简单地求得。

这道题的方案限制是在树上做出的，所以我们不免会想到对子树考虑是否可以设计状态使其具有最优子结构，并且便于转移。

发现这些限制在儿子向父亲转移时具有极良好的性质：

• 根和子树内其它节点不在同一块中，单独成块。
• 以两个儿子为根的子树合并时，两边各取一个互不冲突的集合，并起来亦不冲突。

那么下面贪心合并的方案是显然的：两个子树分别按照段内最大值（即该段贡献）从小到大排序，然后两个子树一一对应合并，分段较多的子树剩下的段不合并。

还需要证明最优子结构性，即在儿子子树的最优方案中被分到同一段的元素，父亲处被分到同一段一定不劣。

我们用某个方案中所有段的大小升序排序后得到的序列代表它。如果两个方案 $a,b$ 满足对于任意位置 $i$ 都有 $a_i\le b_i$，我们称方案 $a$“严格不劣于”$b$。不难发现这样的关系构成了偏序，我们证明同一个子树内所有方案构成的偏序集的极小值是唯一的。

叶子节点本身构成的子树只有一种方案，所以极小值唯一；两种极小值唯一的偏序集按照上述方法进行合并，如果 $x$ 严格不劣于 $a$，$y$ 严格不劣于 $b$，并且 $x\not=a$ 或 $y\not=b$，那么显然 $x,a$ 合并后严格不劣于 $y,b$，并且两者不相等。

朴素的 DP 是，设 $f_{i,j}$ 为 $a$ 长为 $i$ 的前缀，最后一处截断位于 $j$ 时的最小运行时间。

转移为

$$\displaylines{f_{i,j}=(s_i-s_j)^2\min_{s_k\le2s_j-s_i}f_{j,k} }$$

其中 $s_i=\sum_{j=1}^ia_j$。

不难发现 $f_{i,j}$ 在 $j$ 有意义的区间中单调不增。

考虑数学归纳法，$i=0$ 时成立。

设 $t_i$ 为长度为 $i$ 时所有合法的阶段方案中最后一个阶段位置的最大值。显然 $t_{i+1}\ge t_i$

假设单调性对于 $f_0,f_1,f_2,\cdots,f_{i-1}$ 均成立，考虑

$$\displaylines{\begin{aligned} f_{i,j+1}&=(s_i-s_{j+1})^2+f_{j+1,t_{j+1}}\\ &\le(s_i-s_{j+1})^2+f_{j+1,t_j}\\ &=(s_i-s_{j+1})^2+(s_{j+1}-s_{t_j})^2+f_{t_j,t_{t_j}}\\ &=(s_i-s_j-a_j)^2+(s_j-s_{t_j}+a_j)^2+f_{t_j,t_{t_j}}\\ &=(s_i-s_j)^2+(s_j-s_{t_j})^2+f_{t_j,t_{t_j}}-2a_j((s_i-s_j)-(s_j-s_{t_j})-a_j)\\ &=(s_i-s_j)^2+(s_j-s_{t_j})^2+f_{t_j,t_{t_j}}-2a_j((s_i-s_{j+1})-(s_{j+1}-s_{t_j})+a_j)\\ &\le(s_i-s_j)^2+(s_j-s_{t_j})^2+f_{t_j,t_{t_j}}\\ &=(s_i-s_j)^2+f_{j,t_j}\\ &=f_{i,j} \end{aligned} }$$

由第二归纳法，单调性成立。

于是我们只关心 $f_{i,t_i}$ 的值。$t_i$ 具有单调性，可以双指针求得。

令 $b_i=\gcd(a_1,a_2,\cdots,a_3)$， 不难发现 $b_{i+1}\mid b_i$。

于是我们设 $f_x$ 为将序列 $a$ 中所有 $x$ 的倍数重排得到序列 $t_1,t_2,\cdots,t_m$ 之后，$\sum_{i=1}^m\gcd(t_1,t_2,\cdots,t_i)$ 的最大值。

那么显然 $f$ 在 $x$ 处的值只会从它的所有倍数 $kx$ 处转移而来，并且 $f_{kx}$ 对应的最优的序列一定是 $f_x$ 对应的最优的序列的前缀。

转移方程为

$$\displaylines{f_x=\max_{kx\le\max\{a\}}\left\{f_{kx}+\sum_{i=1}^n[x\mid a_i\land kx\not\mid a_i]\right\} }$$

这样转移是 $O(n\log n)$ 的。

考虑到对于合数 $k=pq$（$p,q$ 不为 $1$），$f_{kx}\to f_{px}\to f_{qx}$ 的转移不比 $f_{kx}\to f_{x}$ 劣，所以实际上可以仅枚举所有质数 $k$ 进行转移。

对所有串建出 AC 自动机，如果能够找到一个不经过终止状态的环，则存在一条无限长的不包含所有模式串的 01 串。