用途

对于大多数情况，树中只有很少一部分点是对当前要处理的信息是有意义的。

我们可以在保留这些有意义的点，不破原树结构的情况下得到一个很精简的树，这样我们就不用遍历整颗树了。

这种做法就叫虚树。

和后缀和。

0 序

求

$$ b_k = \sum_{i|k}a_i $$

或

$$ b_k = \sum_{k|d}a_d $$

都一样，没啥区别。

0 序

这个东西看了半天没想明白为啥不是最小生成树，然后发现最小生成树实际上是最小斯坦那树的特殊形式 -- 最小生成树里的所有点都是关键点。

最小斯坦那树是指在一个无向图中，求其最小生成网络使得其

1. 包含所有关键点
2. 总权值在满足 1 的情况下最小。

-1 序

寄啦，哈哈。

今年是新疆维吾尔自治区第一次组织省选。

今年有很多神奇的事情，比如特派员换了，新疆成立竞赛组委会了，办省选了，有 $\frac{1}{3}$ 了，有实体 NOI Linux。当然也不都是好事，疫情精准防控的代表上海已经被奥米克戎攻陷，全国疫情更是此起彼伏，见不到头。这种情况下信息学竞赛还能基本上「出淤泥而不染」，维持较为正常的赛季流畅已是相当不易。

在疫情的限制下，XJOI 最终未能选择新疆大学作为考点，而是选择了一所高中 -- 乌鲁木齐市第一中学。

A Four Points

题目大意

给定矩形的三个顶点，求其剩下的顶点。

思路

签到

B Get Closer

题目大意

给定直线过点 $(0,0)$, $(a,b)$，求从 $(0,0)$ 出发，方向朝右，长度为一的线段的右端点。

思路

一开始是二分硬做的，然后被卡精度了。

求出两点距离，对 $a,b$ 分别除于这个这个距离即可。