260403 以前 x 天
P4383 [八省联考 2018] 林克卡特树
P4768 [NOI2018] 归程
P5163 WD与地图
对边进行整体二分，发现只需要处理传入边集合的导出子图就可以了。
AT_agc029_f [AGC029F] Construction of a tree
发现有解的一必要条件是能对每个点选择一条父亲边，这是一个二分图匹配问题。匹配之后跑 bfs，如果跑不出来那么可以说明不能通过调整匹配使得有解。
AT_utpc2025_b Binary Tree Counting
建立二叉树（区分左右儿子）向多叉树（区分儿子顺序）的双射，发现前者的中序遍历变为后者的后序遍历，前序遍历和后序遍历可以用格路计数进行刻画，设计一个 \(O(n^3)\) 的 dp 即可。
AT_agc061_e [AGC061E] Increment or XOR
发现加法之后一段后缀会变成 \(0\)，考虑按照进位高度对操作序列进行多级划分。设状态表示从低 \(i\) 位是某个状态转移到某个状态，并且是否对高一位进行进位。
P9479 [NOI2023] 桂花树
维护前缀虚树。
Matrix Operations
P10299 [CCC 2024 S5] Chocolate Bar Partition
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\) 查询。