I found it hard, it's hard to find. Oh well whatever nevermind.
目录CF1904E Tree Queries
Tag：T-欧拉序；S-线段树。
注意到 \(\sum k\) 和 \(n\) 同级，大抵是一个和 \(k\) 相关的做法，虚树大概是不可行的，所以考虑一些别的东西。
使用欧拉序描述整棵树，那么这个时候 \(x\) 所在的连通块可以划分成若干个欧拉序上面的区间，这个区间量级是 \(O(k)\) 的。
处理答案只需要离线询问后每次换根即可，这里的维护是容易的，Code，\(O(n\log n)\)。
CF1904F Beautiful Tree
Tag：G-优化建图；G-拓扑排序；A-倍增。
怎么感觉是简单题。
考虑 \(O(n^2)\) 怎么做，显然嗯建个图出来跑拓扑排序就秒杀了。
所以要做到 \(O(n\log n)\) 上我们的倍增优化建图就完事了哈哈，实在是有点难绷。
其实写起来有点像 ST 表优化建图？不管了反正就板子优化建图，Code。
ABC332G Not Too Many Balls
Tag：G-网络流；D-背包。
hot tea！显然有网络流建模：
-
建立二分图，左侧 \(n\) 个点，右侧 \(m\) 个点，以及源点 \(S\) 汇点 \(T\)。
-
令 \(i\) 为第 \(i\) 个左部点，连边 \((S,i,A_i)\)，令 \(j\) 为第 \(j\) 个右部点，连边 \((j,T,B_j)\)。
-
连边 \((i,j,ij)\)。
直接求最大流肯定过不去，考虑有什么好的优化，直接在最大流角度有点 hard，考虑转最小割。
令左侧点集为 \(P\)，右侧点集为 \(Q\)，左侧和 \(S\) 连一起的点集为 \(X\)，右侧和 \(S\) 连一起的点集为 \(Y\)。
那么最小割即：
\[\min_{X\subseteq P}\min_{Y\subseteq Q} (\sum_{i\in P\setminus X} A_i+ \sum_{j\in Y}B_j+ \sum_{i\in X}i\sum_{j\in Q\setminus Y}j) \]直接做仍然很难做，考虑枚举 \(\sum_{i\in X}i\)，则答案变为（令 \(L=\sum_{i\in X}i\)）：
\[\begin{aligned} \min_{L=0}^{N(N+1)/2}\min_{X\subseteq P,\sum_{i\in X}i=L}\min_{Y\subseteq Q} (\sum_{i\in P\setminus X} A_i+ \sum_{j\in Y}B_j+ L\sum_{j\in Q\setminus Y}j)=\\ \min_{L=0}^{N(N+1)/2} (\min_{X\subseteq P,\sum_{i\in X}i=L}\sum_{i\in P\setminus X} A_i+ \sum_{j\in Q}\min(B_j,jL)) \end{aligned} \]这个时候前后就拆成了两部分，第一部分可以背包解决，第二部分可以求出每个 \(j\) 在何时切换，然后扫一遍完事，总时间复杂度 \(O(N^3+M)\)，Code。
标签：Code,min,2023.12,sum,建图,setminus,subseteq,杂题 From： https://www.cnblogs.com/cnyzz/p/17893988.html