P10037 「FAOI-R2」霜雪千年

**注：本题原名梨花开，介于赛时题面有误，且原题面可读性较低，于 2024 年 3 月重写题面并改名。改标题不便赛时选手重新找到该题，但出题人意识到时修改已久，不便改回。在此致歉。** > 在这老街回眸 烟云中追溯我是谁 只消暮雨点滴 便足以粉饰这是非 待这月色涌起 谁人轻叩这门扉 苔绿青石板街 斑驳了流水般岁月 小酌三盏两杯 理不清缠绕的情结 在你淡漠眉间 瞥见离人的喜悲霜雪 洛天依看到了一颗雪中的梨树，梨树的根中有有限的热量，它可以向上需要传递热量到其他节点。但风雪很大，每时每刻每个节点热量都会增加会增加或减少，热量过低的节点会掉落。

具体来说，这棵梨树可以被抽象为一颗以 $1$ 号结点为根的树，初始时每个点都是白色。每个点有热量 $a_i$，初始时 $1$ 以外所有点的热量都为 $0$，$a_1=k$。我们设一个累计热量 $b$。 我们通过如下操作定义一个序列 $\{v_t\}$ 的权值： - 从小到大度过 $1,2,3,\dots,t$ 这 $t$ 个时刻。 - 在第 $x$ 个时刻，执行 $b\gets b+v_x$。 - 对于父子 $(u,v)$，设 $u$ 为父亲，可以选定整数 $h\in[0,a_u]$ 执行操作 $a_u\gets a_u-h$，$a_v\gets a_v+h$，之后该时刻内形如 $(v,w)$ 且 $v$ 为父亲的父子不能操作。 - 若一个点 $i$ 满足 $a_i+b

无

无

### 样例解释 样例 $3$ 解释： 对于一种 $\{v_3\}=\{1,0,-2\}$ 的情况，一种最优操作如下： - 第一个时刻，$1$ 号结点传递 $4$ 热量给 $2$ 号结点，操作完毕后 $a=\{1,4,0,0,0\}$，$b=1$。 - 第二个时刻，$2$ 号结点传递 $2$ 热量给 $4$ 号结点，操作完毕后 $a=\{1,2,0,2,0\}$，$b=1$。 - 第三个时刻，$2$ 号结点传递 $1$ 热量给 $3$ 号结点，$4$ 号结点传递 $1$ 热量给 $5$ 号结点，操作完毕后 $a=\{1,1,1,1,1\}$，$b=-1$。 - 所有时刻结束，因为始终没有 $a_i+b