Ucup2 -19题解：
这场的题还是挺有意思的，之前回家后因为过年的准备+美赛摆了挺久没训练，现在开始复健，顺便复活一下死去已久的博客。
水题就不赘述了，这次主要说说几道比较难的但思路很有趣的题目，顺序就按难度排吧。
G. LCA Counting
题意：给定一颗无向的树，1为根，定义f(k)为选择k个叶子后集合S的最大大小，其中S定义为{lca(xi,xj)|xi,xj属于选定的k个叶子}，其中xi和xj可相同。令叶子数为w,则需要回答从k:1->w 的 f(k)的值。
1<n<=2e5
题解：从小的情况开始考虑，对于k=1时，显然为1，k=2时为3，k=3时可能为4或5...我们手玩后可以发现以下事实：
1，每次f(k)会较于f(k-1)增加1 or 2
2，对于一个节点其所包含的子树生成树为一颗二叉树的形状
定义这里的生成树为所选集合的点根据祖先关系形成的树。
我们可以发现对于一颗生成树内的叶子操作时每步增加2，而更换生成树时的步增加，所以我们肯定要从大的生成树开始逐渐往小的做，这样肯定是f(k)保证最大的。
现在的问题便是找到每颗生成树以及其大小。令u点生成树大小为s(u)
我们首先找的肯定是以根为根的生成树，其必然最大，我们进一步发现这个问题可以递归，对于点u，其子节点为 vi，当u为叶的时候s(u)=1，当u有1个儿子v时s(u)=s(v),当u有多个儿子时s(u)=s(v1)+s(v2)（假设儿子已经根据s从大往小排过序），并且剩下的v3以及之后的儿子会自己形成新的生成树，我们保存其大小到集合E中即可。
最后我们将s(1)放入E中，对E从大到小排序后即可得到f(k)的值。
具体细节可以看看我的代码Submission #245436634 - Codeforces
C. Yet Another Balanced Coloring Problem
题意：给两棵树，节点数分别为n和m。他们中编号为1-k的点恰好都是叶子节点，现在要对两颗树中的每个叶子染色，编号一样的叶子染一样的色，可以染r or b,并且要求染色后对于每个节点其子树中的 r数量与b数量相差不超过1,问是否有解，若有解给出方案。
2<n,m<=2e5
题解：神奇的解法（当然后面的题多少都带点神奇）。
我们观察发现对于包含偶数个儿子的子树，其子树权值必然为0（定义r 为1 ,b为-1），故其对父亲无影响，我们删除其与父亲的边。之后我们发现对于除了叶子和根外每个点，其度数均为偶数。而两个根必然同奇偶，我们可以把叶子看作连接两个树的连接节点，这样他们也有偶数的度数。现在我们定义边的方向，对于第一个树，若u的值为+1,则u->fa，否则为-1，fa->u，对于第二个树相反。在这种定义下，我们发现除了根以外每个点出度等于入度，而对于根一个出度=入度+1，另一个反之，刚好可以作为欧拉图的起点和终点，我们再定义对于树1的叶子，所有入点为-1，出点为1，在对题进行如此转化后，只需对图遍历1次即可得到方案，且正确性显然。
Problem D. Filesystem
题意：给定排列1,2,..n和p，定义一些元素为used为需上传恰1次，其他元素不可上传，每次操作定义为在两个排列中选1个并选择连续的一些点上传。问最少操作次数。
n<=1e3
题解：网络流。
我们定义在1 ,2,---n中被上传定义为染b，在p中上传为染r。
那么我们其实就是想要得到一系列染色段，同一段为同色，代价即为段数。
考虑一个经典的做法，将图中的点拆点，分别于源点汇点相连（iINF=1e8），并且两两相连（INF 不可断)，我们定义在对图进行割后属于S的联通块为r，否则为b。那么我们考虑如何连边加入我们的代价，我们考虑代价会在何时产生：
1，在序列1中i选择b而i+1选择r，
2，在序列2中pi选r而pi+1选b
故我们只需从pi向_pi+1连代价为1的边，从i+1向i连代价为1的边，再通过最小割同时减去由于对源汇点相连边的代价即可。
H. Minimum Cost Flow²
题意：见Problem - H - Codeforces，有空了翻
题解：首先需要观察出一个结论：对于一个环，其代价之和（常规意义下非平方代价）为0。
证明见官方题解（公式太多懒得打了）：
我们考虑最后的最优解一定是存在的且可以表示为一个对于每条边的流量的向量形势，我们考虑如何得到它：通过解方程组！
根据最开始的式子我们已经得到了n-1个方程，而我们有m个变量，所以需要利用上述结论找到剩下的方程，故我们只需找m-(n-1)个方程即可，即我们找到m-(n-1)个环即可。
这很难不联想到生成树，我们建立一颗生成树，对于每条1非树边，我们选定其与树边组成一个基本环，共m-n+1个环。从而我们得到了m个方程，可以解出答案了！
对于做题来说可能已经够了，但对于写题解我们还需要进一步讨论：为什么这样可以满足最优条件对于每一个环代价和都为0。
我们找到任意一个环，我们令边在生成树中的边为C1,其他为C2，那么我们可以通过与基本环＋ or -运算消除所有非树边，得到空集or在树上来回行走的环，必然为0,故此解是满足最优条件的，至于解的唯一性，出题人告诉我们最好的答案就是放手一搏！（）
暂时懒得看了，读者有兴趣可以自行前往官解查看（巨长）。