既然题目的名字是谈笑风生主图当然也要是谈笑风生啦QwQ

BZOJ原题地址

洛谷原题地址

思路

求位于同一条链上的三个点,使前两个点之间的距离小于等于k。

对于给定的 a 和 k,当 b 在 a 上方,显然答案是min(depth[a]-1,k)*(siz[a]-1);当 b 在 a 的下方,显然是求 a 的子树的前 k 层的每个节点的子树大小(不含其本身)之和。
可以用 DFS 序建主席树维护一定深度下子树大小之和。

代码

  1. kal0rona
    Dec 27, 2018

    主席题用主席树233

    Reply