更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19354572

给定一棵有 $n$ 个节点的树，巡警车从 $1$ 号节点出发遍历所有边后返回，每条边需经过两次，总距离为 $2*(n-1)$。现可新建 $K$ 条边$(k = \{ 1, 2\})$，要求新建的每条边必须恰好经过一次，求规划新建边的方案，使得巡警车的总巡逻距离最小，并输出该最小值。

我们可以发现，对于 $k = 1$ 的情况，显然你求出一条直径，再把直径的两个端点连上，这样是最优的。

但是当 $k = 2$ 的时候，我们需要再连一次，但是这样的话，我们最好选比较长的，最初的想法是选次长的直径，但是我们想想，如果你选的这条新的直径，和原来的直径，有很多重合的点，那么就不是很优，我们为了处理这个重复的玩意，其实可以把原直径的所有边赋为 $-1$，这样的话，我们再找最长的直径，就不会出问题了。

但是这样需要知道一个问题， dfs 求直径是无法解决边权为负的情况，于是我们考虑树形 dp 的方式，直接再记一次直径的长度即可。

设两次的直径长度为 $L_1, L_2$，则最终答案为：

$k = 1$ 时：$2 * (n - 1) - L_1 + 1$

$k = 2$ 时：$2 * (n - 1) - (L_1 - 1) - (L_2 - 1)$

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19349977

由于题目的数据范围，我们可以得知，大概是个 $n ^ 3$ 的玩意。

但是我们需要仔细想想怎么计数？

首先，这个玩意和什么有关?

第一肯定是步数，第二是点是否走过，第三是这个点和为我们要的强连通图的关系。

然后我们考虑最难的问题，就是这个强连通图怎么判断，怎么累加答案？我们走到一个点的时候怎么判断其是否能与原来的形成一个强连通呢？还是说其目前自己和其他点成强连通，需要后续的操作去整。

不难发现，其实一个点，其强连通关系只有两种，第一种就是和起点在一个强连通里面，第二种，就是不在起点的强连通里面。

我们定义 $f_{i, j, k}$ 表示目前已经走了 $i$ 步，已经访问了 $j$ 个点，与起点 $1$ 形成的强连通的大小为 $k$。（以下所说的形成强连通均是与 $1$ 形成）

考虑转移。

首先走到点，第一种情况，是没有走过，于是我们有：

$f_{i + 1, j + 1, k} \to f_{i + 1,j + 1, k} + f_{i, j, k} \times (n - j)$

第二种，是走过，但是没有形成强连通的点：

$f_{i + 1, j, k} \to f_{i + 1, j, k} + f_{i, j, k} \times (j - k)$

第三种是，走过，且已经形成了强连通：

$f_{i + 1, j, k} \to f_{i + 1, j, k} + f_{i, j, k} \times k$

于是我们的答案就在 $f_{m, n, n}$。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19346416

首先考虑 $\mathcal{O}(n ^ 2)$ 的解法。

枚举每条边，然后分别统计左右子树的重心，然后想加即可。

然后考虑优化，显然我们的复杂度浪费在了找重心的地方。

“一棵有根树的重心一定在根结点所在的重链上。一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。”——OIwiki

有关树的重心的内容见OI-wiki/树的重心

重心必在节点的「重儿子链」上（重儿子指子树大小最大的子节点），因此可通过倍增沿重儿子链快速定位重心候选。

删除边 $(u, v)$ 后，$u$ 所在的大子树（大小 $n - sz_v$）需要「换根」更新重儿子（原重儿子可能是 $v$，需替换为次重儿子或父方向），而 $v$ 所在的小子树（大小 $sz_v$)）是原树的子树，无需换根。

节点最大子树（含父方向）≤ 总大小 / $2$ 则为重心。

递归算每个节点的子树大小，记录重 / 次重儿子（子树最大 / 次大的子节点），构建倍增数组（沿重儿子链跳，$\mathcal{O}(\log n)$ 找重心）。

然后累加答案即可。

先考虑一下朴素的 dp。

不难发现，对于一个集合最重要的是集合里最小的元素，剩下的元素对应的 $a_i$ 都大于这个值，可以考虑把所有值按照从大到小排序，则集合里其他元素都在最小元素之前。

对于第 $i$ 个数，考虑这个数是集合里最小的元素，或不是最小的元素对应的方案数。 $dp_{i,j}$ 表示 $1\sim i-1$ 个数处理完后，还剩下 $j$ 个数未确定属于哪个集合的方案数。

若第 $i$ 个数不是集合里最小的元素：

$$dp_{i+1,j+1}\gets dp_{i,j}$$

若第 $i$ 个数是集合里最小的元素，枚举这个集合里还有几个元素，即：

$$dp_{i+1,j-k}\gets dp_{i,j}\times \text{C}_j^k(0\le k<a_i)$$

初始状态为 $dp_{1,0}=dp_{1,1}=1$，目标状态为 $dp_{n+1,0}$。转移的过程中对于第二类转移需要枚举 $k$，复杂度为 $O(n^3)$。

考虑如何优化这个 dp 的第二类转移，将组合数拆开得到：

$$dp_{i+1,j-k}\gets dp_{i,j}\times \frac{j!}{k!(j-k)!}$$

假定对于阶段 $i$，设有

$$F(x)=\sum_{i>0}dp_{i,j}j!x^j$$

$$G(x)=\sum_{i>0}\frac{1}{k!}x^j$$

实际上是将 $F,G$ 做一个减法卷积的到 $H$，则有

$$H(x)=\sum_{i>0}dp_{i+1,j}j!x^j$$

对于减法卷积，可以翻转一个多项式的次数，此时减法卷积就转化成了加法卷积，直接用 NTT 计算即可。

可以选择为 $dp_{i,j}$，也可以直接维护 $dp_{i,j}\times j!$。算法的复杂度为 $O(n^2\log n)$。

先考虑 $O(nq)$ 做法。枚举每个点为根去 DFS 做 dp。

不难发现两个相邻的点不能操作二，所以状态要设 $f_{i,2}$ 表示点 $i$ 操作二，把子树的边覆盖完的最小操作。

若一个点不进行操作二，则他到子节点需要用操作一来覆盖，而一个操作一可能端点在两个儿子。考虑先把这个操作一的链拆开，然后从儿子向上合并时去匹配。设 $f_{i,1},f_{i,0}$ 表示点 $i$ 进行操作二，覆盖后子树内留下一个到儿子的操作一半条链没有匹配或全部匹配完。

然后考虑 dp 转移，分类讨论即可：

$$f'_{x,0}\gets \min(f_{x,0}+f_{y,2},f_{x,1}+f_{y,0},f_{x,1}+f_{y,1}-1)$$

$$f'_{x,1}\gets \min(f_{x,1}+f_{y,2},f_{x,0}+f_{y,1},f_{x,0}+f_{y,0}+1)$$

$$f'_{x,2}\gets f_{x,2}\min(f_{y,0},f_{y,1})$$

然后直接转移就可以，复杂度为 $O(nq)$。

考虑换根出答案？但是这个贡献形式比较难拆开，考虑用矩阵描述 dp 的转移，这样做前缀后缀的转移就转化为求矩阵前缀后缀积了，本来矩阵乘法需要严格控制顺序，但这个东西先合并那个子节点无所谓，所以瞎做就行。

复杂度为 $O(nV^3)$，其中 $V=3$。

好像是 COGS 首 A，写篇题解。

其实这道题的思维难度不是特别大，只需要一些技巧和比较高级的算法即可解决。

思路分析

注意到对于一对用来替换的字符串二元组 $(s,t)$，若 $s=t$，则这对字符串一定没用，题目已经限制。

对于这对 $s,t$，可以分别将其表示成 $s=s_A+s_C+s_B,t=t_A+t_D+t_B$，其中 $s_A,t_A$ 是 $s,t$ 的最长公共前缀，$s_B,t_B$ 是 $s,t$ 的最长公共后缀，每次替换操作，实际上是将一个字符串中的 $s_C$ 替换成了 $t_D$。

对于一对询问的字符串 $(S,T)$，若长度不相等，则一定没有合法的变化，题目已经限制。

依然求出两个 $S,T$ 的子串 $s_{A,C,B},t_{A,D,B}$（意义同上），若 $(S,T)$ 可以用过 $(s,t)$ 替换得来，必须满足 $S_C=s_C,T_D=t_D$，且 $s$ 在 $S$ 中出现，$t$ 在 $T$ 中出现。

这样的话，我们就可以得到一个 $O(nq)$ 的算法，对于每个变化的字符串二元组和询问，处理出变化的部分，若 $(s,t),(S,T)$ 变化的部分一样，且 $s$ 再 $S$ 中出现，$t$ 在 $T$ 中出现，因为变化的部分要匹配上，所以匹配的起始位置是确定的，可以用字符串 Hash 来完成 $O(1)$ 的判断。

cin>>S>>T;int ans=0;
if(S.size()!=T.size()){
    printf("0\n");
    continue;
}
int L=0,R=S.size()-1;
while(S[L]==T[L])L++;
while(S[R]==T[R])R--;
for(int j=0;j<S.size();j++){
    if(j){
        hs[j]=hs[j-1]*P+S[j];
        ht[j]=ht[j-1]*P+T[j];
    }else{
        hs[j]=S[j];
        ht[j]=T[j];
    }
}
for(int j=1;j<=n;j++){
    bool flag=0;
    if(l[j]==-1)continue;
    if(R-L+1!=r[j]-l[j]+1)continue;
    int ll=L-l[j],rr=ll+len[j]-1;
    if(ll<0||rr>=S.size())continue;
    if(askS(ll,rr)!=a[j])continue;
    if(askT(ll,rr)!=b[j])continue;
    ans++;
}
printf("%d\n",ans);

考虑优化这个过程，离线，还是利用字符串 Hash，把变化部分相同的变化字符串和询问字符串放在一起处理。

此时变化部分的匹配一定满足，只需要保证 $s_A$ 是 $S_A$ 的后缀，$t_B$ 是 $T_B$ 的前缀。将所有 $s_A,S_A$ 放在一起建一个字典树，$t_B,T_B$ 放在一起建一个字典树，则前后缀关系可以转化成字典树上的祖先子孙关系，两个字典树就有两维的限制，直接做离散化加二维数点即可，复杂度为 $O(L+(n+q)\log(n+q))$。

这个做法所使用的算法均在提高级的考纲之内，应该是钦定的正解。

其实有一种更加优秀的做法，可以转化为经典的多模式串匹配的算法，但需要 AC 自动机。

考虑将每个字符串对 $(s,t)$ 拼成一个大串 $P=s_A+?+s_C+t_D+?+s+B$，其中 $?$ 是防止匹配的一个字符。把询问串也这样拼成大串 $Q$，每个询问就是有多少个 $P$ 是 $Q$ 的子串，直接 AC 自动机的复杂度为 $O(|\sum|L)$，其中 $|\sum|$ 是一个 $26$ 的常数。

后者实现比较简单，所以我只完成了第二个算法。