题意

有一棵 $N$ 个结点的有根树，根节点为 $1$ , 你要从根节点出发 $K$ 次，每一步只能从父亲走到儿子，每个结点都有一个权值，每经过一个结点都会把总价值算上当前点的权值，重复经过的点不会重复计算，求 $K$ 次出发后能够得到的最大价值。

输入包括三个值： $N$ , $K$ , $seed$ ，对于 $1$ 结点，它的权值为 $seed$ ；对于结点 $i (2 \leq i \leq n)$ ，这个结点的权值为 $(val_{i - 1} * 23333333 + 6666666) \% 1000000007$ ，父亲为 $(val_{i} ^ 23333333) \% (i - 1) + 1;$

思路

在去FJ的飞机上写出来的题解。

真（ru）的（yi）是（ke）签（ai）到（miao）。

看到 $n$ 大得吓人，于是我们不乱想，考虑贪心。具体来说就是我们发现每次从根结点往下走一定是走到一个叶子的地方，具体来说就是我们可以把树上的一堆边看作一条条链之后贪心的选。

具体来说就是对于一个结点记录以它为起点往下走到叶子能够得到的最优价值，所以我们可以遍历每个结点的时候可以更新其父结点能够得到的最优价值，因为当前父结点已经确定了除去走向当前结点的那条路径的最优价值，我们只需要看一下走向当前结点的是不是更优就可以了，注意要是我们成功更新了，就需要把原本的那条价值较高的链和父结点断开，因为我们到重复的点是不重复计算的，没有重复更新就断开当前结点和父亲的连边。

代码实现就是可以把当前结点确定的路径全部都设置成它原本的价值，然后遍历结点更新答案，每次确定了一条链的时候（假如我们知道了当前父节点连哪一条与儿子的边最大或者确定了某一个结点与它父亲的连边要断开就能确定）就直接把它丢进一个数组里，最后把这个数组排序取前 $k$ 大就做完了，因为我们最多访问 $k$ 个叶子。

代码很好写，因为观察父节点的生成方式， $i$ 的父节点一定是小于 $i$ 的，那我们甚至连递归都不用了。