0103abc 的网站

一个暴力的做法是直接二分图建模，注意到直接把可以组队的点连起来，相邻两个点的 值差一定为 $1$，因此一定能得到一张二分图。直接增广 $k$ 次跑 dinic 即可。 但是边的数量是 $O(n2^n)$ 级别的，直接跑难以通过，考虑优化。观察图的结构可知，对图的一条匹配边...

先考虑图是一个树的情况。此时定义 $f_u$ 表示当前已经处理的边中所有从 $u$ 结点出发的沿边权递增的路径能够到达的点的数量。这个是容易处理的，直接把边权从大到小排序然后按顺序转移即可。 然后考虑把上述做法扩展到仙人掌上。考虑如果当前一条边 $$ 在仙人掌的某个环上，则处理该边的时候 $u,v$...

~~這也能做嗎.jpg~~ 套路的考慮先求出圖的任意一個 DFS 生成樹，然後結合綫性基來維護答案。具體的，任意求出圖的一個 DFS 樹后記 $disu$ 表示從根結點到 $u$ 結點上經過的所有邊的邊權的 XOR 值，則考慮一條非樹邊 $$ 其和樹上的路徑 $u\leftrightarrow v$...