UOJ Goodbye Wuxu

不说比赛的时候的尴尬场景。（E 题忘记读 subtask 编号爆零。。。A 题 1:40 过，B，C 题脑子一片糨糊。。。）

Problem A - 新年的拯救计划

一开始一直在想用链构造。。。

最后我的构造是左右两个菊花，菊花的根用一条边相连，每个点先作为一侧的叶子，然后轮流做根，然后在作为另一侧的叶子。code

Problem B - 新年的Dog划分

一开始没有搞清楚返回的是整张图连通。。。

枚举每一条边能不能删，最后能形成一棵生成树。显然可以二分优化。

然后判断二分图，把除了树边以外连接两部分的边删了，然后依次删去树边，判断图是否连通。

code

Problem C - 新年的小黄鸭

$O(n^2)$ DP 需要记录根节点向上的重链长度（我居然比赛的时候没有想到。。。）

根据题解（其实写的有点迷），显然第二维可以记录取 $\log$ 之后的值，然后转移就是枚举子树内向下 $2^{x}$ 层的结点（或叶结点），它们之间为重链，然后将两侧轻边及其子树的贡献加上（可以预处理）。其中转移到非叶子结点一共 $O(n \log n)$ 个，叶子结点用 $O(\log n)$ 个线段树维护。

具体实现的时候【轻边及其子树的贡献】部分会对一个子树产生贡献，用线段树维护。

然后将权值拆分计算贡献。其实在这一步之后 DP 的意义就变成了 $f_i$ 表示 $i$ 子树的答案，然后转移枚举根节点向下延伸的重链到了哪个叶结点。其中旁边的轻链和之前一样计算，然后重链的贡献转换成 重链上的 $\log$ 个点处产生贡献。然后就也变成子树加。所以都可以用线段树维护。

其实核心代码就一个 DFS (我的 dfs2)。 code