1.21 树专题 zz
CF1578J Just Kingdom $\color{blue}\Diamond$
首先分析这个操作造成的影响。容易发现这样对于一个点 $u$，可以把它的儿子分成两类：要么以这个儿子为根的子树内所有点的限制都被满足了，要么没有。对于前者就是填满，后者会平均分剩下的。
那么此时就有一个 $O(n^2)$ 的暴力：对于每个点，从它往上跳并维护当前需要的钱 $lim$。转移是 $lim\leftarrow \sum_{v\in son_u}\min(siz_v,lim)$。
考虑优化。$\color{blue}\Diamond$ 对于这种将一个值变为和其他某个值相关的 $\min$ 的东西，可以考虑当 $\min$ 去到它本身时，它的值至少翻倍。而注意到 $siz_v\le nV$，所以这样的关键点只有 $O(\log n+\log V)$ 个。
后面的实现部分不是重点，倍增预处理一些东西，查询时二分即可。
CF1423C Dušan's Railway
构造题。
首先题目给的这个限制太奇怪了，尝试进行一个翻译。一个很不知道怎么样得到的想法是，你要构造一种存储 $10n$ 条路径的数据结构，使得任意一条树上的路径都能用其中的不超过 $3$ 条拼出来。
树太困难了，考虑序列。如果限制是 $2$ 条的话，显然可以想到分治，进而想到猫树。但是 $2n\log n$ 还是太多了点。但是这里是 $3$ 条，发现一般的分块查询就是一个块的后缀+若干个块+一个块的前缀正好 $3$ 条。然后对于每个块递归做。
可以证明递归不超过 $O(\log\log n)$ 层，虽然我不知道怎么证。每层 $\frac 52n$ 条边。
放到树上，树分块。复杂度不变，但是可能常数大一点，但是这个上界卡的不死。可以通过。实现方法是在当前连通块 $siz\ge B$ 时分出去。
qoj9905 哈夫曼树 $\color{blue}\Diamond$
最重要的显然是找到一个可维护的条件，表示出这个树是否合法。
然后就有一个非常厉害的条件：$\color{blue}\Diamond$ 将所有非叶节点的左右儿子对应权值对应的二元组 $[x,y)(x\le y)$ 提取出来，对二元组排序，如果两两间无交则有解。
充分性考虑可以按照排序后的顺序进行操作构造出一组解。必要性考虑若不成立，有交的两组中小的两个应该一起操作。
但是带修。不过发现这不重要，因为这棵树的深度不会很深，否则会不满足哈夫曼树性质。上界大概是 $O(\log n+\log V)$。所以更新的时候暴力跳父亲即可，用 set 维护二元组。
CF1284F New Year and Social Network $\color{blue}\Diamond$
二分图最大匹配，首先联想到 Hall 定理。是否有完美匹配？考虑对于 $T_1$ 上的一个边集 $S$，断开后分成若干个连通块，与其在二分图有边的 $T_2$ 上的边满足其连接的两个点不属于 $T_1$ 中的同一连通块。容易发现这些边至少有 $|S|$ 条，故有完美匹配。
然后考虑构造。$\color{blue}\Diamond$ 对于这样和顺序无关的，可以考虑从简单情况入手，递归到子问题。考虑每次取出 $T_1$ 上的一个叶子以及其父边 $(u,v)$。然后考虑 $T_2$ 上的 $u\to v$ 的路径。由于显然有 $u$ 属于 $T_1$ 中 $u$ 所在的连通块，$v$ 属于 $v$ 所在的，所以路径上一定有一条边 $(x,y)$，满足 $x,y$ 不在同一连通块。然后只需要把 $(u,v),(x,y)$ 缩成一个点变成子问题即可。实现上可以在 $T_2$ 上二分找到 $x,y$。
qoj2562 Fake Plastic Trees 2 $\color{blue}\Diamond$
第二次听了，发现并不难理解？
首先有一个显然的 dp：设 $dp_{u,i,j}$ 表示 $u$ 子树内断了 $i$ 条边，当前 $u$ 所在连通块的权值和为 $j$ 的方案数。这个 dp 的问题显然是值域非常大。考虑是否能缩小值域。注意到对于一个点 $u$，由于除了它所在的连通块，其他连通块都是满足条件的，所以它所在的连通块的和的取值最多只有 $i(R-L)$ 种。
还不够。再进一步发掘性质。然后发现，如果对于一个 $u,i$，存在 $j_1<j_2<j_3,j_3-j_1<R-L$ 使得 $dp_{u,i,j_1/j_2/j_3}=1$，则这个 $j_2$ 就是没用的，$j_1$ 和 $j_3$ 中一定有一个可以替代它。但是写的时候才发现我并没有完全理解怎么证明，待补。
于是用个 vector 存可行的 dp 位置，按照树形 dp 暴力合并就行。复杂度 $O(nk^3)$。
$\color{blue}\Diamond$ 关于容量为 $m$ 的树上背包的复杂度为 $O(nm)$ 的证明：把子树分成 $siz>m$ 的大子树和 $siz\le m$ 的小子树。
首先对于小子树中的合并，每个点被计算的点对都只有 $O(m)$ 个，这部分就是 $O(nm)$ 的。
然后，当小子树被合并到大子树时，由于每个点只会被合并一次，所以这部分也是 $O(nm)$ 的。
最后，大子树和大子树的合并只会发生 $O(\frac nm)$ 次，所以复杂度为 $O(\frac nm\times m^2)=O(nm)$。所以总复杂度也是 $O(nm)$ 了。
qoj894 Longest Loose Segment
写着突然发现实际上非常简单。。。
直接枚举最小值位置 $p$，求出以它为最小值的边界 $(l,r)$。然后考虑以此为最小值的区间可能长什么样。首先一定可以证明这个区间一定顶到了某个边界。否则考虑当前最大值在 $p$ 的左边还是右边，往对应的方向平移这个区间一定也合法。
然后发现如果是区间右端点卡在 $p$，左端点没顶边界的情况，往左平移区间一定是不劣的。因为最大值不减，最小值变大。也就是说区间一定形如 $(l,x](x\ge p)$，即一定包含 $(l,p)$ 或 $(r,p)$，那么最大值就是好求的了，答案也是显然的。
具体实现是用笛卡尔树。一开始题解是直接从笛卡尔树方面入手，但是自己写的时候发现直接做也是思路顺畅的。
qoj5418 Color the Tree $\color{blue}\Diamond$
首先不难发现每一层之间是独立的，所以分开做。
然后有一个显然的 dp：设 $dp_u$ 为处理完 $u$ 子树内所有第 $k$ 层点的最小代价。则有 $dp_u=\min(\sum dp_v,a_{k-dep_u})$。
$\color{blue}\Diamond$ 然后注意到每次处理只关注了第 $k$ 层的点，所以考虑建出虚树。于是上面的转移式的后半就会变成 $\min\limits_{i=dep_u}^{dep_{fa'u}+1} a{k-i}$。其中 $fa'_u$ 为虚树上 $u$ 的父亲。于是 st 表维护即可。
qoj9840 Tree Partition $\color{blue}\Diamond$
可能先会考虑树上 dp。$\color{blue}\Diamond$ 但是发现值域上连续一段这个条件相当苛刻。于是不妨转换思路，对序列 dp。
于是要刻画连通块的条件。$\color{blue}\Diamond$ 考虑把连通块挂到最上面的点上，于是可以得到一个充要条件：区间内仅有一个点的父亲不在区间内。设 $dp_{i,j}$ 表示当前处理了前 $i$ 个点，形成 $j$ 个连通块的方案数。不难发现需要 $O(1)$ 转移。
考虑若干条边 $(u,fa_u)$，条件就变成了区间内只有一条边是到区间外的。然后考虑到区间外的边也有两种。$u<fa_u$ 的称其为后向边，否则为前向边。然后分类讨论：只有一条后向边和只有一条前向边。
首先对于后向边的限制，只需要维护当前所有 $fa_u>i$ 的后向边中 $u$ 的前两大值，分成两个区间即可。
但是前向边比较麻烦，不过可以考虑类似扫描线地做。考虑对于每个位置维护 $f_i$ 表示跨过 $i$ 的前向边数量，然后要做的就是从所有 $f_i=0/1$ 的位置中的一个前缀转移，并且支持给 $f_i$ 的一个后缀加。
考虑 $f_i=0$ 的位置，每次操作都会加入一个数或者把一段后缀去掉。直接维护前缀和即可。$f_i=1$ 的也是类似的，操作变成了把 $f_i=0$ 的一段后缀移过来，但是发现移过来的位置中的 $mn$，其后面原来在 $f_i=1$ 的一定已经被全部移除了。所以直接维护前缀和即可。精细一点实现就是 $O(nk+n\log n)$ 的。
qoj1288 Tokens on the Tree
终于到这题了🤩当时场上被创飞了。其实后面的计数并不是难点，最最最关键的还是如何算 $f(w,b)$，尝试在看题解做题后给出一个可能相对自然的思路吧。
钦定 $w\ge b$，先手玩一些小的情况。容易发现当 $w=b=1$ 的时候，大部分情况 $f(w,b)=1$。这是因为可以通过先“让一让”的方式使情况间互相转化。
再考虑一些特殊情况，比如 $w=2,b=1$，树为菊花。容易发现这样答案为叶子个数，即黑点在不同的叶子是不同方案。思考一下这是为什么，会发现这是因为无论如何根都是白色，黑色就无法通过了。容易拓展到一般情况：记 $mx_u$ 表示断掉 $u$ 后形成的连通块中大小的最大值，则当 $mx_u<w$ 时，$u$ 点一定为白。那么方案数就是把 $u$ 断掉后 $siz\ge b$ 的连通块数量。
写的时候突然发现有个小问题：万一这样的 $u$ 不连通怎么办？其实容易发现这样的情况是不可能的。手玩一下就行。
那是否，若不存在 $mx_u<w$ 答案就是 $1$？考虑一条链的情况，即使 $w=b=1$，也会发现对于一种情况，把 $w,b$ 位置调换之后的情况是本质不同的。于是就有两种了。于是发现，这样子“调换位置”是一种很特殊的情况。若能调换位置答案就是 $1$，否则是 $2$。不会具体证明。
然后考虑怎么样是能调换位置的。考虑调换位置的过程，可以抽象成若干步骤：$w$ 先进一个子树，然后 $b$ 进另一个，然后 $w$ 先出来，最后 $b$ 再出来。这要求存在一个点 $u$，使得 $u$ 有两个 $siz\ge w$ 和一个 $siz\ge b$ 的子树。
然后就可以计数了。由于要考虑 $\min mx_u$，所以拎出重心。
当 $w\le mx_u$ 时，没有必须是白色的点。所以对于每个 $u$ 求出 $se_u,th_u$ 表示断掉 $u$ 后第二，三大的连通块大小，则 $ans=1$ 的要求就是存在 $u$ 使得 $w\le se_u\wedge b\le th_u$。枚举 $w$ 扫描线，算 $b$ 的贡献即可。
当 $w>mx_u$ 时，必定为白色点的形成了一个包含根的连通块。于是对于每个 $u$ 算以 $u$ 为根的子树的贡献即可。具体地，会对 $w\in(mx_{fa_{u}},mx_u],b\in[1,\min(w,siz_u)]$ 的 $f(w,b)$ 有 $1$ 的贡献。直接算就行。
实现上有点困难，还要处理 $w<b$ 的情况，所以要还要算 $w=b$ 的答案之和。不过也是一样的。想清楚了就没有那么难写。$O(n)$。
2.3 字符串
CF1827C Palindrome Partition
“接上一个偶回文串”这个操作让我们想到 dp。设 $dp_i$ 表示以 $i$ 结尾的好串的个数，问题就是要如何不重不漏地转移，因为可能有若干个以 $i$ 结尾的偶回文串。
此时可以发现一个关键性质：只用考虑以 $i$ 结尾的最短的偶回文串。证明手玩一下不想写了，总之就是更长的一定可以拆成若干个短的。所以只用处理出来以 $i$ 结尾的最短的偶回文串长度即可。这个随便怎么处理都行。
CF1913F Palindromic Problem
直接算。先算减少的。考虑以 $i$ 为中心的极长回文串长度为 $n$。那么如果改变了一个在该串中位置为 $x$ 的字符就会减少 $\min(x,n-x+1)$ 个回文子串。manacher 找出来极长回文串，需要维护区间加公差为 $1/-1$ 的等差数列。二阶差分即可。
再算多的。对于一个极长回文串，如果改变后新的极长串长度变了，那么一定要改原极长串左边或右边的第一个字符，变化的长度就是原串左边部分倒过来和右边部分的 lcp。二分哈希。最后枚举所有方案算答案即可。
P10716 简单的字符串问题
首先注意 $S[1,i]$ 开头结尾都有 $A$，所以 $A$ 一定是 $S[1,i]$ 的一个 border。并且容易发现有单调性：如果更长的 border 合法，那么更短的也合法。
于是考虑建出失配树，询问的时候在树上倍增，于是需要求 $S[1,j]$ 在 $S[1,i]$ 中出现了多少次。容易发现存储下 $S[1,j]$ 所有不重复出现位置，最多有 $O(n\log n)$ 个元素，是可以接受的。于是对于一个长度 $len$，只用查询某一个后缀 $[x,n]$ 第一个 $\operatorname{lcp}(S[1,n],S[i,n])$ 的 $i$ 的位置即可。从小到大处理 $len$，二分哈希预处理出每个后缀和 $S$ 的 lcp。问题变成支持删数，找 $p$ 的后继。set 就行。
询问的时候也是二分就行。Go and learn binary search。
CF1975G Zimpha Fan Club
首先我们有个非常牛的东西：带适配符的模式串与文本串匹配。
首先考虑没有通配符。显然可以 kmp。但是有没有其他方法？有的，有的。考虑给每个字符赋一个权，那么两个字符等价于 $a_i=b_j$。那么考虑 $s[1,n]$ 和 $t[p,p+n-1]$ 匹配就等价于 $\sum a_i-b_{p+i-1}=0$。。。吗。发现并不是，因为如果正负号不一样就影响了。于是变成 $(a_i-b_j)^2$。拆开变成 $\sum a_i^2-2a_ib_j+b_j^2$。同时注意到这里的 $j-i=p-1$，于是可以卷积。
然后加通配符。不难发现可以把通配符的权设为 $0$，变成 $a_ib_j(a_i-b_j)^2$。一样做。
回到原题。首先发现 $s,t$ 都没有 $*$ 的显然是简单的。对于都有的，考虑每次拎出来 $s,t$ 的第一个或最后一个字符。如果有 * 就不管了。否则如果不同显然无解，相同就直接删掉。最后两个串一定有第一个字符为 * 或最后一个为 * 的。这样显然是可以构造出来的。
否则考虑变成形如 $s_1s_2s_3...s_m$ 和 $t$ 匹配。显然对于每个 $s_i$ 贪心地找到 $t$ 中最前的匹配位置最优。怎么找？显然要用上面那个东西。但是这不支持增量。怎么办。注意到如果对 $s$ 中长为 $n$ 和 $t$ 中长为 $m$ 的做，那么要不找到，要不可以确定 $t$ 中前 $m-n+1$ 个位置不存在可匹配的，做一次的复杂度为 $(m+n)\log(m+n)$。这么看取 $m=3n$ 好像更优每次取 $m=2n$做即可。$O(n\log n)$。
P7735 轻重边
一个非常厉害的结论：将操作变成链上打时间戳，于是注意到一条边为重边 $\iff$ 两个端点时间戳相同。于是直接嗯线段树维护即可。
当然有更无脑的做法。这里变成黑白。重剖，考虑维护重边的颜色，轻边暴力并在询问时处理。不难发现只需要暴力处理链上的轻边、跳重链时起点重儿子对应的边以及 lca 的父边（口胡的应该没错吧）。一堆细节。
CF1930H Interactive Mex Tree
首先对于查询 $\min$ 这个操作，由定义知 $\operatorname{mex}(S)=\min(\mathbb{N}\setminus S)$。于是就是需要找到一种方法找出 $5$ 个集合，其并集为所有不在路径上的节点。
由于是在不知道是怎么想出来的所以直接放结论了。。先考虑 $u$ 为 $v$ 祖先的情况。先令 $p_1$ 为 dfn 序。先问 $[1,dfn_u-1],[dfn_v+1,n]$。发现剩下一堆 $u\to v$ 链上某个点的不在链上的儿子的子树。于是令 $p_2$ 为出栈序 dfe。由定义知 $[1,dfe_u]$ 包含了所有 $dfn_i\in[1,dfn_u-1]$ 并且不为 $u$ 祖先的 $i$。所以再拼上 $[1,dfe_v-1]$ 即可。
对于 $u,v$ 没有祖先关系的情况也是类似的，手玩一下即可得到。
CF772E Verifying Kingdom
交互题，于是考虑这个操作能干什么。考虑一个点 $x$，如果询问 $x,y,z$，令 $d=\operatorname{LCA}(y,z)(d\not=x)$，则如果返回 $d$ 最深，那么可以知道 $x$ 不在 $d$ 子树内。否则若 $\operatorname{LCA}(x,y)$ 深则 $x$ 在 $d$ 的儿子中靠近 $x$ 方向的子树，反之亦然。
然后就要考虑如何去用这个操作。换个方向考虑上面的分析，容易发现：如果能找到一个非叶子节点的两个儿子子树内各一个点，那么就能知道任意一点相对这个非叶子节点的位置。那么不断对同一个未知位置的叶子操作，就能得到其真实位置。
但是问题是这样依次确定叶子位置时，很多叶子一开始是不知道的。但是注意到我们只需要知道该叶子相对当前已知叶子的位置，不断加叶子就能得到答案。于是考虑动态维护当前已知叶子构成的虚树，每次加叶子并对虚树形态进行修改即可。
最后，现在这个做法还是询问次数还是 $O(n^2)$ 的。但是不难想到可以套个点分，询问次数就是 $O(n\log n)$ 的了。
P5439 永恒
说实话好像就是直接做。题意即求： $$ \sum_{u<v}\sum_{x<y\wedge x,y\in u\rightsquigarrow v}dep_{\operatorname{LCA}'(x,y)} $$ 那么套路算 $x,y$ 的贡献。首先分 $x,y$ 之间是否有祖先关系的情况讨论 $x,y$ 被 $T_1$ 的多少条路径包含。而 $dep_{\operatorname{LCA(x,y)}}$ 根据经典套路可以在 $T_2$ 上做链加链求和。具体实现的时候似乎可以稍微容斥一下多的贡献，总之就是忘了当时是怎么写的，应该不难写。
CF1930G Prefix Max Set Counting
似乎没有比 dp 更好的处理方法。但是一个问题是 dp 枚举的顺序。但是注意到，dfs 序是进入一个子树就要把这个子树走完才能出去。于是如果当前节点有若干个儿子，那 dp 的时候一定是从 $\max_{u\in son_i}u$ 小的 $son_i$ 开始遍历到大的，dp 时这样 dfs 就行。
然后考虑怎么转移。首先 $i$ 如果能成为前缀最大值，那么它一定比它所有的祖先要大。然后考虑怎么样的 $j$ 能转移到 $i$。分两种情况讨论：
- $j$ 为 $i$ 的祖先。那么 $j$ 是 $i$ 祖先中的 $\max$。
- 否则，$j$ 一定要比 $i$ 的所有祖先大。并且令 $d=\operatorname{LCA}(i,j)$，则 $j$ 一定是 $d$ 在 $j$ 方向的儿子子树内的最大值。否则在进入 $d$ 在 $i$ 方向儿子子树时，当前的前缀 $\max$ 一定不是 $j$。
然后考虑怎么维护。$j$ 为 $i$ 祖先的部分是简单的。否则，考虑在 $j$ 出栈时更新。先将 $j$ 的所有儿子对应子树的贡献去除，再加上 $j$ 子树的贡献。同时要求 $j<i$，所以再用 BIT 维护即可。
2.7 贪心构造博弈 hkk
P4704 太极剑
结果发现我完全没有理解这个断环成链！！！
称切的线和圆的交点为切点。首先有个重要性质：所有绳子都被切断 $\iff$ 绳子分开的两条弧上都有切点。证明可以考虑断环成链，变成对于每个区间 $[l,r]$，$[l,r]$ 和 $[1,l-1]\cup[r+1,2n]$ 都有切点。然后将 $2k$ 个切点排序，实际上的切线选 $(1,k+1),(2,k+2),\cdots,(k,2k)$。容易发现这样一定每个 $[l,r]$ 都和某个 $[x,k+x]$ 有交。
但是这样在圆上的问题还是太难做了一些。但是发现任意一个点一定会在一条绳子的其中一边，于是先枚举一个一定选的点，剩下的限制就全部变成断环成链后，要求某个区间内一定要选点。
容易发现虽然这些区间对应序列上的位置会变化，但是在所有的 $[l,r],[r,l+2n],[l+2n,r+2n]$ 中（也就是断环成链后 $[l,r]$ 可能对应的区间），每一次断环成链对应的 $[p,p+2n)$ 中会且仅会包含其中的一个。于是预处理 $f_i$ 表示 $i$ 后第一个必须要有切点的位置，问题就变成了进行多少次 $i\leftarrow f_i$ 后 $i$ 比一开始增加了至少 $2n$。倍增即可。
$$ f_{u,i}=\sum_{dfn_v<dfn_u+siz_u\wedge dep_u\le dep_v< dep_u+2^i}c_u\oplus(dep_v-dep_u) \ f_{u,i}=f_{u,i-1}+f_{to_u,i-1}+(cnt_{to_u,i-1,0}-cnt_{to_u,i-1,1})\times 2^{i-1} \ $$
