题面以图片显示，请点击“阅读全文”查看。

JSOI 信息学代表队一共有 $N$ 名候选人，这些候选人从 $1$ 到 $N$ 编号。方便起见，JYY 的编号是 $0$ 号。每个候选人都由一位编号比他小的候选人$R_i$推荐。如果 $R_i = 0$ ，则说明这个候选人是 JYY 自己看上的。

为了保证团队的和谐，JYY 需要保证，如果招募了候选人 $i$，那么候选人 $R_i$ 也一定需要在团队中。当然了，JYY 自己总是在团队里的。每一个候选人都有一个战斗值 $P_i$ ，也有一个招募费用 $S_i$。JYY 希望招募 $K$ 个候选人（JYY 自己不算），组成一个性价比最高的团队。也就是，这 $K$ 个被 JYY 选择的候选人的总战斗值与总招募费用的比值最大。

小凸和小方相约玩密室逃脱，这个密室是一棵有 $n$ 个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯泡即可逃出密室。

每个灯泡有个权值 $a_i$ ，每条边也有个权值 $b_i$ 。点亮第 $1$ 个灯泡不需要花费，之后每点亮 $1$ 个新的灯泡 $v$ 的花费，等于上一个被点亮的灯泡 $u$ 到这个点 $v$ 的距离 $D _ {u,v}$ ，乘以这个点的权值 $a_v$ 。在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。

请告诉他们，逃出密室的最少花费是多少。

某个国家有 $n$ 个城市，这 $n$ 个点之间的边构成一棵树。

现求一条边长度和不超过 $S$ 的路径（两端都是城市，可以只为一个城市），使得所有城市到这条路径的距离的最大值最小，并输出这个最小值。

游戏一开始，Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $K_i$ ，当绵羊达到第 $i$ 个装置时，它会往后弹 $K_i$ 步，达到第 $i+K_i$ 个装置，若不存在第 $i+K_i$ 个装置，则绵羊被弹飞。

存在两种操作：

• 查询在第 $i$ 个装置起步时，再经多少次会被弹飞。

• 修改第 $i$ 个装置的弹力系数为 $K'$ 。

保证任何时候，任何装置弹力系数均为正整数。

定义一棵树上最长的路径为树的直径。树的直径可能不唯一。

给定的一棵 $n$ 个结点的树，求其直径的长度，以及有多少条边满足所有的直径都经过该边。

有一颗 $n$（$n<20000$）个节点的树，每条边都有边权。接下来由聪聪和可可分别随即选一个点，如果两点之间简单路径上的边权和是 $3$ 的倍数，则判聪聪赢，否则可可赢。

聪聪非常爱思考问题，希望知道对于这张图自己的获胜概率是多少。

点分治是一种主要在树上的分治，可以在解决一些树上特定条件的路径的问题。其复杂度与大部分分治类似，大概是 $O(K \; \log{n})$（ $K$ 为除分治步骤之外的时间复杂度的多项式）。

给出一颗 $n$ 个节点的无权树， $m$ 次询问，每次给出三个点编号为 $a$ ，$b$ ， $c$ ，询问到这三个点距离最小的点的编号以及其距离和。