P4845Solutionlink考虑树形dp，对于每个\(u\)直接钦定它的三种可能状态：有灯，没灯但是被其他灯照亮，没灯也没被照亮。这样钦定会导致一些需要被照亮的点在当前子树中还未被照亮，需要依靠子树外的灯来照亮。称这种点为闲置点。状态内只需要记录闲置点中最深的到子树根的距离，以及......

P4632Solutionlink对时间扫描线，就变成支持单点加入删除一个颜色点，求所有颜色距离某个点的距离最大值。考虑二分答案，现在就是要检验\([x-mid,x+mid]\)内是否有\(1\simk\)颜色的点各至少一个。数颜色可以考虑维护\(pre_i\)表示上一个与该点同色的位置。然后区间\([l,r]......

P4555Solutionlink双回文串的左右两半部分显然是互相独立的。于是考虑求出\(lm_i\)表示以\(i\)结尾的最长回文子串长度，\(rm_i\)表示以\(i\)开头的最长回文子串长度，最后扫一遍所有的分隔符求\(lm+rm\)的最大值即可。考虑如何求\(lm,rm\)。先用manacher拉出\(p\)，......

Link。首先我们假设在看本文章的所有人除了@左乐都已经使用点分树A掉了震波。然后我们要怎么简单修改A掉这个消息传递呢。震波是维护距离\(\leqk\)的点，这里只需要维护\(=k\)的，显然我们可以改掉维护前缀和的那个数据结构（比如树状数组），直接用普通数组/vector。跳......

P4137Solutionlink考虑建主席树：权值线段树的叶子维护这个权值最后出现的下标，push_up的时候取\(\min\)。这样一个区间的\(\min\)小于\(k\)意味着有一个权值最后出现的下标小于\(k\)，也就是说\(k\)后面没有出现这个权值。也就是说mex就在这个区间内。这样询问的时候......

P3990Solutionlink一次只能跳一步的情况下：\(dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j}+dp_{i-1,j+1}\)接下来考虑能跳奇数步：你发现跳\(3\)步相当于先跳一个奇数\(1\)再跳一个\(2\)，跳\(5\)步相当于先跳一个奇数\(3\)再跳一个\(2\)也就是说能够一步跳到\((i,j)\)的一定能......

P3773Solutionlink\[\binomnm\bmod2=\binom{n\bmod2}{m\bmod2}\binom{n/2}{m/2}\bmod2\]我们要让\(\binomnm\bmod2\)不为\(0\)，也就是让右式的两项均不为\(0\)。考虑\(\binom{n\bmod2}{m\bmod2}\)：\(n\bmod2\)和\(m\bmod2\)的取值要么是\(0\)要么是\(1\)......

P3768Solutionlink\(\begin{aligned}\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)&=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^nijd[\gcd(i,j)=d]\\&=\sum_{d=1}^nd^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij[......

P3435Solutionlink画个图：显然四个黄色部分是相等的。也就是说，黄色部分是A的一个border。根据题目，周期的长度也就是Q的长度，也就是A的长度减去它的某个border的长度。现在要求这个最大，由于A的长度固定，要求的也就是A的最小border长度。根据KMP求出来的nxt......

P3426Solutionlink考虑dp。设\(dp_i\)表示至\(i\)的字符串的答案。KMP求出nxt数组，那么显然\(dp_i\)要么等于\(i\)要么等于\(dp_{nxt_i}\)。什么时候\(dp_i\)等于\(dp_{nxt_i}\)呢？这时这个字符串一定由一个与\(nxt_i\)有相同\(dp\)值的前缀再印上一个bo......