P3899 [湖南集训] 更为厉害

[湖南集训] 更为厉害

题目描述

设 \(\text T\) 为一棵有根树，我们做如下的定义：

• 设 \(a\) 和 \(b\) 为 \(\text T\) 中的两个不同节点。如果 \(a\) 是 \(b\) 的祖先，那么称“\(a\) 比 \(b\) 更为厉害”。
• 设 \(a\) 和 \(b\) 为 \(\text T\) 中的两个不同节点。如果 \(a\) 与 \(b\) 在树上的距离不超过某个给定常数 \(x\)，那么称“ \(a\) 与 \(b\) 彼此彼此”。

给定一棵 \(n\) 个节点的有根树 \(\text T\)，节点的编号为 \(1\) 到 \(n\)，根节点为 \(1\) 号节点。
你需要回答 \(q\) 个询问，询问给定两个整数 \(p\) 和 \(k\)，问有多少个有序三元组 \((a,b,c)\) 满足：

1. \(a,b,c\) 为 \(\text T\) 中三个不同的点，且 \(a\) 为 \(p\) 号节点；
2. \(a\) 和 \(b\) 都比 \(c\) 更为厉害；
3. \(a\) 和 \(b\) 彼此彼此。这里彼此彼此中的常数为给定的 \(k\)。

数据范围：

\(n\le 3*10^5\)

Solution:

话说之前暑假的时候貌似就见过这题，当时它貌似叫“谈笑风生”。

事先声明：本文中的 \(dep\) 是在根节点的深度为1的基础上定义的,同时，我将使用 \(S(x)\) 表示点 x 的子树
首先我们来思考一下那些点会产生贡献：

拿样例来看，对于询问 （2,2）：合法的三元组有 \((2,1,4)\)、 \((2,1,5)\) 和 \((2,4,5)\)

我们先重新描述一下贡献：我们发现三元组中的 \(a\) , \(b\) 并无区别，所以我们假设 (a,b,c) 的深度是单调递增的

不难看出其实我们可以把贡献拆为两部分:以点 \(p\) 做为三元组中的 \(b\) 的贡献和以点 \(p\) 作为 \(a\) 的贡献

我们先求以点 \(p\) 做为三元组中的 \(b\) 的贡献：
在这种情况下，(fa[p]->1) 路径上的所有点都可以作为 \(a\) ,\(p\) 的子树内的所有节点都可以作为 \(c\) ,因此，该部分的贡献为：
\(min(dep[p]-1,k)*(siz[p]-1)\)

然后对于以点 \(p\) 作为 \(a\) 的贡献：
假设我们已经在点 p 的子树内钦定了一个点 \(q\) 作为 \(b\) ,那么 \(c\) 就应该从 \(q\) 的子树内进行选取，也就是说，这部分的贡献是：

我们不难想到用线段树合并来维护这个式子，我们以\(dep[x]\) 为下标 \(siz[x]-1\) 为点权建立一颗权值线段树，然后向上合并，那么对于每个点 \(p\) 上能取到的贡献就是 \(dep\in[dep_p,dep_p+k]\) 这段区间的总和

然后说一些细节：

由于是线段树合并，所以如果想要在线做这道题的话在 merge 的时候一定要新建一个节点作为合并的结果，否则就会使得一个点上挂有同层其他节点的贡献，这样显然是错误的

但是我们发现本题可以离线，所以我们将每个询问挂到点上，我们在构建完一个点的线段树后直接查询，在其他节点乱入之前完成答案统计。

Code: