T1
题意
给一个串，将其重复\(n\)次后构成新串，求其最长前缀=后缀
解法
显然重复的\(n-1\)次是一定相同的，于是只需要对原串跑一次KMP，求出最小循环节即可
Code
T3
题意
给一棵树，每秒钟所有度数为0或1的点会消失；现在有\(m\)次询问，每次给一个约束，要求一条链上的点不会消失，求除了这条链外其他所有点都消失所需要的时间
解法
倍增。。。但如果想偏了会很容易想远
我的做法和std不太一样
将一条链拆成两半，之后只考虑其中一半，每次询问即求\(max(\) 一个点到这条链的距离 \()\)
这条链最下面的点会计算所有子树中的点，除此之外其他点都不会算链上的点
于是设\(f_{x,i}\)表示\(x\)到其\(2^i\)祖先这条链被标记时，不考虑父亲的答案
但是只是这样\(f\)不能递推，于是设\(g_{x,i}\)表示在\(f_{x,i}\)的基础上不考虑\(x\)的所有儿子的情况
转移方程：
f[x][i]=max(f[x][i-1],g[fa[x][i-1]][i-1]);
g[x][i]=max(g[x][i-1],g[fa[x][i-1]][i-1]);可以发现，由于max不能被拆分，所以\(lca\)不能被包含在链中，需要单独处理，我这里开了个堆来处理这个问题...
还需要考虑\(lca\)向上走的情况，这个用换根法就可以了
Code