【题解】PermuTree (easy version) - Codeforces 1856E1-526互联

链接：

https://codeforces.com/contest/1856/problem/E1

题目大意：

给定一棵以节点 \(1\) 为根的树，树的大小不超过 \(n(1\leq n\leq 5000)\) ，给树的节点赋各不相同的权值（可以简化为某个 \([1,n]\) 的排列），使得满足下述条件的节点对 \((u,v)\) 最多：节点 \(u\) 的权值 \(<\) 节点 \(lca(u,v)\) 的权值 \(<\) 节点 \(v\) 的权值。

解题思路：

从这个计数方式可以想到，两个节点和他们的LCA之间的权值的相对大小才重要，其他的东西不重要。如果这棵树是个二叉树，那么很明显就直接输出中序遍历即可。否则应该把子树们分成左右两个部分，其中左部分的子树的节点的权值均小于LCA的权值，然后右部分的子树的节点的权值均大于LCA的权值，然后容易简化得到，每一棵子树所分配的权值一定是一个连续的整数区间。每一棵子树中，以根节点为LCA的满足条件的节点对的总数，必定刚好等于左部分的子树的节点数乘以右部分的子树的节点数。然后每棵子树内部怎么分配左右，跟外部的树没有任何关系。

习惯上用 \(siz[u]\) 表示节点 \(u\) 的子树的大小，那么可以写为：对每棵子树最大化 \([\sum\limits_{vl\in left} siz_{vl}]\cdot [\sum\limits_{vr\in right} siz_{vr}]\) 。

由于某棵子树内部，所有节点的数量是恒定的，由均值不等式或者二次函数可以知道，左右子树的节点数量总和应该尽可能接近。

那么问题就转化成了：给定一个正整数的集合，将其划分成2个子集，使得两个子集的总和尽可能接近。也就是LeetCode的经典题目。

答案对每个节点为根的子树均求解一次。易知总体的复杂度和某棵子树内的复杂度的上界是一样的。

但是我的确不知道怎么写，去查了下谷歌。

大概能确定一种使用dp的思路，也就是dp[i][j]表示使用前i个元素时，能否组合出和为j，如果能组合出，则为true，否则为false。这是个背包问题。类似于 https://www.cnblogs.com/purinliang/p/17590924.html 但比这个简单。

那么这种问题也是按套路使用bitset即可。