标签 虚树 下的文章

给定 n 个节点的树,每个点有个权值 a_i,保证 \{a_{1 \cdots n}\} 是一个 1n 的排列,求:

\frac 1 {n(n-1)} \sum_{i=1}^n \sum_{j=1}^n \varphi(a_i \times a_j) \times \operatorname{dist}(i, j)

READ MORE

本题有虚树做法,基本思想差不多,但个人感觉还是换根树剖清真一点 233。

定义一组询问的根节点为这组询问的一号节点。

一个点会对答案产生贡献,当且仅当这个点到这组节点的其他节点的距离大于等于这个节点到这组询问的根节点的距离。

假设当前我们做到根节点为 root ,当前节点为 u 的情况,找出这条路径的中点为 mid ,那么肯定不会对答案产生贡献的点即整颗树 root 为根节点时 mid 这个节点的整颗子树。就是一个简单的换根树剖,乱搞一下即可。

READ MORE