## [HAOI2015]树上染***r /> [题目链接](https://ac.nowcoder.com/acm/problem/19996) 题意： 给你一颗大小为$n$的树，然后将树上的$k$个点染成黑色， $n - k$个点染成白色。问黑色两两之间的距离，与白色两两之间的距离和最大是多少？ 题解： 这题写了一晚上，发现自己dp方程就设错了。看了题解才知道怎么写。网上题解很多，但是很多都忽略一个很重要的细节。下面我详细说一下。 设 $dp[u][j]$**表示$u$为节点的子树中选$j$个黑点， 黑点两两之间的距离与 剩下的$k - j$个子树外的黑的点经过 子树$u...

E 仓鼠与珂朵莉 主席树 + 启发式合并思想 题意： 给你一个长度为n的数组， 每次操作选择一个区间 然后问 选择一个数 然就出 再这个区间的次数的乘积。 题解： 如果给你一个区间 对于暴力的求法一般是枚举每个数， 再去查找这个数出现了几次，然后算出最大的贡献。 这样对于每次询问都是 的复杂度。 如果我们每次只找 出现一次 且最大的数， 出现两次且最大的数， 出现三次且最大的数………… 假设已经知道看出现一次且最大的数， 出现两次且最大的数………… 那么枚举的时间复杂度为 大概是 左右，但是这样有个问题？ 如何找到出现一次且最大的数， 出现两次且最大数？ 我想了很久好像没有可行的...