题解：CF2143C Max Tree

· · 题解

讲一种不同于官方题解但容易写的做法。

题目要求所有边的贡献和最大，可以贪心的想到让每条边的贡献都为 \max(x,y)。显然，对于题目中的任何情况都可以做到让每条边的贡献都为 \max(x,y)。我们观察一下边做贡献的条件：

\begin{cases} x & \text{if }p_u<p_v,\\ y & \text{otherwise.} \end{cases}

如果 x>y，赋值时我们就令 p_u<p_v，否就令则 p_u>p_v，这样，我们就把边的属性转化为了点权间的关系。

然后考虑用 DFS 处理这些关系，以节点 1 为根遍历整棵树，并钦定 p_1=0。当我们走到点 u'，接下来枚举所有与 u' 相连的边（与父亲相连的边除外），并设与这条边相连的另一个点为 v'。根据这条边的信息，我们也可以像上面那样处理出 p_{u'} 和 p_{v'} 的大小关系。注意，u' 不一定就是这条边的 u。

另开数组 ans 表示付给点的权值。这样，我们就将 p 处理成了一个将 1 到 n 依次赋给数组 ans 的优先级（也就是所有 ans_i 间的大小关系），p_i 越大，ans_i 便越大。当两点 i,j 有 p_i=p_j 时，ans_i 和 ans_j 谁大谁小都行。这样一来，问题便迎刃而解，不太明白或不会实现的可以看我代码。

再说一些实现小细节。因为 u' 不一定就是正在处理的边的 u，也可能是他的 v，所以要分情况讨论，在写 DFS 的时候注意一下。

因把 y 打成 v 导致调试耗时一个小时祭，可以看见我的代码里一堆调试信息，但代码本身还是挺好写的。提交记录。