260111 以前 x 天
P7565 [JOISC 2021] ビーバーの会合 2 (Day3)
给定一棵树，对于每个 \(k\in [1,n]\) 求出，树上任意 \(k\) 个点的重心最多有多少个。
\(n\le 2\times 10^5\)
若 \(2\nmid k\)，那么答案只能为 \(1\)。否则，全体重心分布在一条链上，链的两边是两棵子树，各包含 \(k/2\) 个关键点。因此，可以认为一条链 \(u,v\) 会对 \(k\le\min(sz_u(v),sz_v(u))\) 产生 \(dis(u,v)\) 的贡献。于是可以用点分治统计链的贡献。
但我们有更简单的办法。若 \(u,v\) 不存在祖先关系，那么 \(sz_u(v)=sz(v),sz_v(u)=sz(u)\)，于是万事大吉。若 \(u,v\) 存在祖先关系，假设 \(u\) 是 \(v\) 的祖先，那么 \(sz_v(u)=n-sz(son(u,v))\)，\(son(u,v)\) 表示 \(u\) 向 \(v\) 方向的儿子。注意到此时如果选择重心为根节点，那么总有 \(\min(sz_v(u),sz_u(v))=\min(sz(u),sz(v))=sz(v)\)。这时我们把所有 \(sz(u)\) 搞出来维护后缀直径即可。
P4228 [清华集训 2017] 榕树之心
给定一棵树，树根为 \(1\)。初始时只有树根一个节点，树根上有一个棋子。每次加入一个叶子，然后棋子向叶子方向移动一条边。问结束时棋子可以位于哪些节点上。
\(n\le 10^5\)
考虑如何判定根节点。首先必须有 \(2\nmid n\)。然后如果根是重心，即各子树大小不存在绝对众数，那么显然合法。剩下的情况我们可能会让重子树内部进行一些抵消，这可以通过 dp 来完成：设 \(f_u\) 表示棋子走进 \(u\) 子树，在 \(u\) 子树长满后最浅位于多深（到 \(u\) 的距离）。容易通过数学归纳法证明 \(f_u+2,f_u+4\cdots\)（不超过 \(sz[u]\)）也都是等效能到达的深度（不是实际到达，可以和外子树抵消）。于是可以根据上面的过程写出转移：
现在考虑如何对所有点求答案。假如要判定节点 \(u\)，考查 \(1\to u\) 的链上挂的子树，如果这些子树不存在绝对众数那么显然合法；否则如果绝对众数是挂在 \(u\) 下面的，那么从 \(f_{son}\) 转移，判定过程同上式；否则绝对众数是挂在链下面的，那么我们可以在走到绝对众数位置的时候走下去，发现直接把绝对众数作为 \(f_{son}\) 转移就是等价的。于是直接 dfs 即可。
CF587F Duff is Mad
给定 \(n\) 个字符串，每次询问一个区间的字符串 \(s_{l\sim r}\) 在另一个字符串 \(s_k\) 中的出现次数。
\(n,q,\sum|s_i|\le 10^5\)
对 \(|s_k|\) 根号分治，若 \(s_k\le B\)，那么先转化成前缀询问然后直接扫描线分块维护 fail 树 dfn 序即可。用分块的原因是平衡 \(O(n)\) 次修改 \(O(qB)\) 次查询。若 \(s_k>B\)，这样不同的 \(s_k\) 只有 \(\frac{n}{B}\) 个，考虑对每个 \(s_k\) \(O(n)\) 求答案。把 \(s_k\) 放到 acam 上跑一遍，然后求 fail 树的子树和，再把每个 \(s_i\) 对应的子树和也就是出现次数用前缀和维护即可。
P3447 [POI 2006] KRY-Crystals
枚举最高在哪一位解除限制，然后前后的贡献都是好算的。
CF1336E2 Chiori and Doll Picking (hard version)
搞出 \(n\) 个数的线性基 \(A\)，显然有 \(O(2^{rank(A)})\) 的做法。
考虑对 \(span(A)\) 做一遍 \(fwt\)：
考虑到 \(|S\cap T|\bmod 2\) 运算对于 xor 运算具有分配律，因此 \((-1)^{|S\cap T|}\) 可以把 \(T\) 拆成若干基底的结果相乘得到。进一步观察可知，若存在 \([x^T]span(A)=1\) 满足 \(|S\cap T|=1\)，那么 \([x^S]fwt(span(A))=0\)（两两配对），否则为 \(|2^{rank(A)}|\)。
发现 \([x^S]fwt(span(A))\ne 0\) 的 \(S\) 需要对 \(A\) 的 \(rank(A)\) 个基底分别满足条件，因此这样的 \(S\) 其实只有 \(2^{m-rank(A)}\) 个，因此 \(rank(\{S\})=m-rank(A)\)。尝试求出全体 \(S\) 构成的线性基（记为 \(B\)），可以将 \(A\) 的非主元作为主元，\(A\) 的主元那几列可以由 \(A\) 的非主元的那几行转置得到。
然后通过 \(B=fwt(A)\) 求 \(A\) 的 popcount 贡献其实比较容易。