方知蓦然回首之时
那人却已不在灯火阑珊处

标签 虚树 下的文章

给定 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

我们先考虑一个 O(n \times 2^{n-m+1}) 的做法:每次硬点每个限制的左端点选或不选,然后树形 DP 。

考虑每次树形 DP 时不一样的点是很少的,可以建出一个虚树把那些点提出来,需要注意的是最好把整棵树的根同时硬点为虚树的根,可以少判一些情况。

然后对于不在虚树上的部分预先 DP 出来,可以理解为一个关于某一个虚点的 DP 值(取或不取)的二元一次函数,然后每次硬点就只需要跑虚树即可,复杂度 O(n + (n - m + 2) \times 2^{n - m + 1})

READ MORE

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

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

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

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

READ MORE