two

每个阶段删掉 \(Red/Blue\) 一定是交替的

显然如果一个边满足只有一个点在 \(dfn\) 对应的区间里面

那么把对面的树的边的 \(dfn\) 放到自己这边，每次删除的边放到自己这边搞区间删除

对边的两个端点的 \(dfn\) 搞一个双射，每次删除一定是区间里面的一个前缀或者后缀，所以线段树维护即可

为了简化代码量，使用了 \(std::merge\)

这个函数是归并，需要 \(st_1,ed_1,st_1,ed_2,back\_inserter()\) 五个参数

sum

因为互质，所以每个质因子只会被选一次，那么有以下结论：

\((1)\) 每个数最多有两个质因子

\((2)\) 如果有两个质因子，必然是一个大于 \(\sqrt n\) 另一个小于之

感性理解是 \(trivial\) 的一下

这样的话对每个 \(\le \sqrt n\) 的质因子，从 \(S\) 连流量 \(1\)，费用 \(0\)

每个 \(>\sqrt n\) 的质因子，连到 \(T\)，流量费用同上

质因子之间如果选择两个优于选择一个那么就连流量 \(1\)，费用 \(f(x,y)-f(x)-f(y)\)

跑最大费用可行流即可

这个就是 \(spfa\) 改成最长路，如果当前 \(d[T]\le 0\) 就不增广了

bracket

写了仨半小时，点分没还原就爆零了

因为是树上的路径，那么考虑合并两个子树的路径信息

把括号转成 \(±1\)，对于一个前缀，如果其最大值是路径最大/小值，那么最大/小值的出现次数是其 \(f(x,y)\) 的值

那么按照 \(\texttt{SDOI2016模式字符串}\) 的思想，维护到 \(x\) 和从 \(x\) 出发的值

自贡献可以在处理儿子的时候减掉，和一般的点分是一样的

发现 \(f(x,y)=k,f(y,z)=l\) 可以贡献给 \(f(x,z)=k+l\)

对于当前点分子树的信息卷积的时候分着每个和为 \(0\) 的数组卷即可

实现的时候注意 \(dfs\) 的时候不能直接修改信息，因为每次统计是一个链，回溯时候要统计的是子树的，需要记一下 \(pre\)

Dp记录

求

\[\min_{S\in A}\{\frac{M-\sum_{x\in S} x}{|S|}\in\{\texttt{Z}\}\},|A|\le 100 \]

枚举最后的选择的集合大小 \(sz\)

设 \(f[i][j][k]\) 为考虑了\(i\) 个数，选择了 \(j\) 个，所有的和 \(\mod sz\) 为 \(k\) 的方案

\(\Theta(n^4)\) 能过的