CF1856E1 PermuTree (easy version) 题解

假定当前在节点 \(u\)，它拥有两棵子树 \(v,w\)，此时 \(u\) 是 \(\operatorname{lca}(v,w)\)。

我们一定可以构造出一个排列 \(a\)，使得所有满足 \(i \in v\) 的节点 \(i\) 和满足 \(j \in w\) 的节点 \(j\)，有 \(a_i<a_u<a_j\)。

因此此时点 \(u\) 对于答案的贡献即为 \(size_v \times size_w\)，其中 \(size_u\) 表示节点 \(u\) 的子树大小。

进一步推广，若节点 \(u\) 拥有多棵子树，则考虑将 \(u\) 的子树分成两个集合 \(S,T\)，最大化 \(\sum_{i \in S} i \times \sum_{j \in T} j\)。

我们考虑进行树上 01 背包，若能分成大小为 \(x\) 的集合 \(S\)，则节点 \(u\) 对于答案的贡献即为 \(x \times (size_u-x)\)。

时间复杂度 \(O(n^2)\)。代码。