2020-2021:teams:farmer_john:2020暑假精选题目:树上问题
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:树上问题 [2020/09/05 11:24] jjleo |
2020-2021:teams:farmer_john:2020暑假精选题目:树上问题 [2020/09/05 11:54] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 47: | 行 47: | ||
| ====题意==== | ====题意==== | ||
| + | 定义一个序列$[s_1, s_2, \dots, s_k]$的前缀前缀和为$s_1 + (s_1 + s_2) + (s_1 + s_2 + s_3) + \dots + (s_1 + s_2 + \dots + s_k)$。\\ | ||
| + | 给出一棵$n$个节点的树，每个点有一个权值，求一条有向路径，使得每个点权值所构成的序列的前缀前缀和最大。$(2 \le n \le 150000)$ | ||
| ====题解==== | ====题解==== | ||
| + | 看到路径问题，直接上点分治，我们考虑两条路径合并时如何计算前缀前缀和。我们规定其它节点到分治中心的方向为向上，反之为向下。考虑所有向上路径对向下路径的贡献，设向上路径的前缀前缀和为$b$，所有节点权值之和为$x$，向下路径的前缀前缀和为$a$，节点数为$k$，则该路径的总前缀前缀和$y$为$$y=(kx+b)+a$$其中括号内是一个一次函数的形式而$a$是一个定值，因此问题转化为多个一次函数求横坐标为某一值时的最大值，直接使用LineContainer即可。 | ||
| + | |||
| + | 注意我们每条路径向上向下均有可能，因此每一个分治中心要进行两次，一正一反。另外分治中心我们并没有考虑，编写时无论将其放在向下或向上均可，还需要注意存在分治中心为一个端点的向上或向下的路径答案，不要忘记特判。 | ||
2020-2021/teams/farmer_john/2020暑假精选题目/树上问题.1599276289.txt.gz · 最后更改: 2020/09/05 11:24 由 jjleo
