省选-树上问题

代码好难调。。。

这道题我们需要求一条路径的哈希值，需要求出根节点到他的哈希值，还有他到根节点的，然后要写半天。

首先我们发现每一对节点的 LCA 个数是 $\log n$ 级别的，所以考虑枚举 LCA。

$\sum\limits_{dis(z,y)\leq k-dis(x,z)\&LCA(x,y)=z}a_y$

$LCA(x,y)=z$，答案就是拿 $z$ 的子树内到 $z$ 的距离 $\leq k-dis(x,z)$ 的点权和 $-$ $x$ 方向子树中到 $z$ 的距离 $\leq k-dis(x,z)$ 的点权和。

对每个点 $x$ 建一棵动态开点线段树，下标为 $i$ 的位置维护 $x$ 子树内所有 $dis(x,z)=i$ 的 $a_z$ 的和。

• 对于 $z$ 子树内的 $x$，区间查询即可。

• 对于 $z$ 在 $x$ 方向上的儿子 $s$ 的子树，考虑对于每个点再建立一棵动态开点线段树，线段树上下标为 $i$ 的位置维护 $x$ 子树内到 $fa_x$ 距离 $=i$ 的点权和，然后就可以解决了。

查询：从 $x$ 沿点分树向上，设当前节点为 $s$，$d = \operatorname{dis}(s, x)$。若 $d \le k$，则答案加上 $w1[s]$ 中距离 $\le k-d$ 的和，减去上一节点 $pre$ 的 $w2[pre]$ 中距离 $\le k-d$ 的和。

修改：从 $x$ 沿点分树向上，对每个 $s$，$w1[s]$ 中下标 $\operatorname{dis}(s, x)$ 增加权值；若 $s$ 有父亲 $fa$，则 $w2[s]$ 中下标 $\operatorname{dis}(fa, x)$ 增加权值。

代码太难调了！！！

我们发现，交换这个点只会改变左右子树间的贡献。

所以我们只需要计算所有点的左右子树间的贡献就行了。

对于每一个点，建一个动态开点权值线段树，线段树的合并就可以计算贡献了，左边 $\le mid$ 的和右边 $\ge mid$ 的进行这种匹配。

注意：部门不必联通！

$f_{x,i}$ 表示在 $x$ 的子树中选择 $i$ 个点组成的所有树上 LIS 中，级别值 $w$ 最小值最大的那一个。

然后利用到这道题状态的有序性。

然后我们建立 multiset $f_u$，里面的数按升序排列后，第 $i$ 个数表示： 在 $u$ 的子树中，选 $i$ 个结点组成合法集合时，这 $i$ 个结点中最大的权值最小可能是多少。

然后合并就是直接插入，很好理解。

最后答案就是 multiset 的大小。

这道题需要定义一个 $g$ 表示在 $dfn$ 为 $x$ 的节点上，到他所在的重链底端的权值和。

然后定义 $f$ 表示 $i$ 节点向下走 $j$ 的路劲权值和减去 $g_i$。

然后这样设计是为了同一条重链上的节点可以直接转移。