260403 以前 x 天
P4383 [八省联考 2018] 林克卡特树
走出来的路径一定形如树上至多 \(k+1\) 条点不交的路径，如果少于 \(k+1\) 条那么就需要一些空路径补齐到 \(k+1\) 条，而且容易对任意 \(k+1\) 条不交的路径构造方案。于是直接 wqs 二分即可。
P4768 [NOI2018] 归程
使用 kruskal 重构树即可。
P5163 WD与地图
对每条边被合并的时间进行整体二分，把已经合并的边用并查集合并起来，复杂度就对了。
AT_agc029_f [AGC029F] Construction of a tree
设 \(S\) 表示 \(\{E_i\}\) 的一子集，\(f(S)\) 表示其中所有 \(E_i\) 的并，于是首先有必要条件：\(|f(S)|\ge |S|+1\)，那么可以找到一组 \(E_i\) 向 \(V\) 的完美匹配。于是从唯一没被匹配的点开始沿着交错树搜索，如果什么时候停下了，就说明剩下的部分有 \(|f(S)|=|S|\) 不满足必要条件，因此该条件是充要的。
AT_utpc2025_b Binary Tree Counting
区分左右儿子的 \(n\) 个点的二叉树和区分儿子顺序的 \(n+1\) 个点的多叉树一一对应，并且前序遍历相同，前者的中序遍历变为后者的后序遍历，于是我们对后者计数。可以在关键点的虚树上 dp，状态只需要记子树大小，转移是 \(O(n^3)\) 的，中间需要格路计数。
AT_agc061_e [AGC061E] Increment or XOR
发现加法之后一段后缀会变成 \(0\)，考虑按照进位高度对操作序列进行多级划分。设状态表示从低 \(i\) 位是某个状态转移到某个状态，并且是否对高一位进行进位。由于中间转移有环，所以要用 dijkstra。
P9479 [NOI2023] 桂花树
\(\max(i,j)\) 可以用扫描线处理，考虑加入一个前缀的节点形成的虚树，新增的节点可以挂在之前的点上，之前的边上，挂在未来的节点下面，或者填充一个节点。需要状压前 \(k\) 步使用 Case3 的情况。
CF1019C Sergey's problem
每次选一个点，加入 \(S\) 并删掉它和它的出边。这样 \(S\) 可以在一步内走到所有点。考虑 \(S\) 的导出子图，由于只有后加入的指向先加入的，因此导出子图是 DAG，直接从上往下构造独立集即可。
Matrix Operations
首先操作分块，块内简单等价类分治。考虑如何统计本块网格上的一个小块在前面操作后的矩形最大值，考虑用线段树扫描线，这样复杂度是 \(O(n\sqrt n\log n)\)。考虑把线段树分上下两层，中间是所有可能查询的区间，这样就可以一次 \(O(B)\) 清空上半部分的标记，把一列的答案全都算出来。时间复杂度 \(O(n\sqrt{n\log n})\)。
P10299 [CCC 2024 S5] Chocolate Bar Partition
首先把所有数都减去平均值，转化为每个块的和都是 \(0\)。然后如果只在至多有 \(1\) 行横跨的位置划分，左侧没划分完的块的 \(sum\) 就等于左侧所有数的和，不用记到状态里。分讨几种转移，转移是 \(O(1)\) 的。
P6736 「Wdsr-2」白泽教育
P9167 [省选联考 2023] 城市建造
qoj4898 基础图论练习题
某模拟赛题目 fenwick
有一个长为 \(n\) 的树状数组，你进行 \(m\) 次操作，每次操作独立均匀随机两个 \([1,n]\) 和 \([0,S]\) 之间的整数 \(p,v\)，然后对树状数组执行 add(p, v)。问最终树状数组各个位置的值的 \(k\) 次方的和的期望。
\(n,m,S\le 10^9,~k\le 1000\)
直接线性性拆期望，然后考虑一次操作对一个位置的贡献，\(k\) 次方期望直接套路把低次幂全都记下来，对原先的值 \(x\) 加上另一个独立的随机变量 \(y\) 相当于一个二项式卷积。直接枚举长度，然后转成 EGF 跑暴力卷积多项式快速幂即可。套路完了。
某模拟赛题目 cute
给定 \(k\) 棵 \(n\) 个节点的树 \(T_{1\sim k}\)，节点从 \(0\) 开始编号，\(\operatorname{path}\) 表示路径上所有节点编号构成的集合，求
\(n\le 3\times 10^5\)
\(\operatorname{mex}\) 的最大值不好处理，直接 \(\min-\max\) 容斥成最小值，然后拆贡献转化为枚举 \(i\) 并钦定三棵树的 \(\operatorname{mex}\) 都大于 \(i\)，转化为要对一些子树统计交集大小。这东西应该是没法直接做，发现查询的子树都是不断变小的，因此把增量部分直接暴力扫一遍删掉，均摊是 \(O(n)\) 的。
某模拟赛题目 pair
给你一些物品，物品有重量，问有多少个有序非负整数二元组 \((x,y)\) 满足 \([0,x]\times [0,y]\) 的总重量都可以被同时表示。物品的重量会变、
\(n\le 2\times 10^5\)
肯定是将物品按照重量从小到大加入。手摸一下合法的二元组形成的形状，发现图形上关键的点只有 \(\log V\) 个，然后可以用线段树做到 \(\log^2V\) 查询。