好题。

模拟赛出了这题，抽象。

初步化简：

由于 \(\min (A,C)\) 不好处理，我们考虑从大到小加边加点，或者从小到大删边删点。

一般题目是考虑加边加点好操作一点，这题是考虑删边删点好操作。

然后我们记当前枚举的 \(\min (A,C)\) 的最小值是多少，记为 \(x\) 。然后称大于等于 \(x\) 点权和边权的是合法的。

然后我们考虑合法的边中哪些是有用的，一条边有用当且仅当他两个端点的两边都存在合法点。

所以倘若某一条边的一端没有合法点，那么我们就可以把这条边给删掉了。

考虑删边和删点，删边的话，就把边的两个端点给缩起来就好了，然后点权合并；而对于删点可以直接暴力删掉（注意：允许空心点存在，即不存在合法点，但是要保证他不是叶子节点），倘若删完之后变成了变成了空心节点，还是叶节点，那么就删掉，其中可能导致连锁反应，父亲也是空点，然后现在变成了叶节点，那么从下往上删点即可。

这样我们就得到了一个新的树称作 \(G\) ，树边表示一条合法边，而树点表示由不合法边缩成的连通块

计算答案

我们现在考虑选出一个子树 \(T'\) ，点集为 \(V\) （注意 \(V\) 的大小指的是合法点的大小），边集为 \(E\) ，那么可以知道的是边的数量是 \(\min (V-1,E)\) 。

我们考虑怎样的选择是合法的，能保证选出来的是一棵树。

首先我们记 \(G\) 的实际的点数是 \(k\) ，\(V\) 指的是合法点个数。

• 我们考虑当 \(\min (V-1,E)\) 受到 \(V-1\) 的限制是什么情况，就是说有很多点是空点，那么实际上所有点都会被选择，然后我们再任意选出前 \(V-1\) 大的边的权值加起来就好了。

那么问题来了这样为什么是对的呢。

因为首先你叶子节点一定不是空点，所以叶子节点一定是被选的，而只要你所有叶子节点都被选了，那么你无论加什么 边都一定可以使他连通（虽然我不会证明，但是的确看上去挺对的结论）

• 考虑受到 \(E\) 的限制，这时候就说明你的合法点太多了，边不够支撑了，但是可以发现每个叶子节点的连通块中一定要选一个合法点，否则与他连着的这条边一定选不了。然后选完之后，你就可以发现，变成了和上面类似，剩下的点，以及所有边考虑怎么选，考虑剩下 \(p\) 条边，我们再选前 \(p\) 大的节点即可。

然后我们发现叶子节点中一定至少要选出一个点，这样一定是优的，否则与他连着的父边就选不了，而你又发现选完叶子节点之后，剩下的点边实际上无论怎么选都可以保证合法的这个性质，所以你就用线段树求前若干大就好了。

所以我们现在有 \(x=\min(A,C)\) 然后 \(T\) 的边数 \(cnt=\min(|V|-1,|E|)\) ，然后记叶子节点已经选了的有 \(lef\) 个，贡献是 \(num\) 。

那么答案有三部分，一个是 \(num\) ，一个是点权中前 \(cnt+1-lef\) 大的和，另一个是边权中前 \(cnt\) 大的和。

实现

我们要维护的东西：

• \(G\) 中点所代表连通块中的点权

• \(G\) 中点连通块连着的边

• 维护每个叶子的最大值的和

• 对于合法边权构成的权值线段树

• 对于合法点去除叶节点已经选完后的权值线段树

• 一个点是叶子当且仅当权值是 \(1\) ，所以节点 \(1\) 也可能是叶子

具体实现，合并两个点可以用 \(set\) 当然你用线段树合并也不是不行，用 \(set\) 启发式合并可以做到 \(\log^2 n\) ，然后对于前若干大，直接上线段树就好了。

总时间复杂度 \(O(n\log^2 n)\) ，\(Alex\_Wei\) 说可以用线段树合并 \(+\) 懒惰删除做到 \(O(n\log n)\) ，反正我没有码力写不来。