P6436 「EZEC-1」越狱

由于监狱长 PF 的疏忽，罪犯小 E 找到了机会越狱。 然而，不学无术的小 E 不懂得保密。PF 很快发现了他的计划，并对他展开了追捕。 因为小 E 自己造船，而狱长 PF 坐的是官方的船，所以在每条航道上的表现不一样，通过时间可能不同。具体见输入格式。 为了不饿肚子，小 E 准备买一个包来装食物。

小 E 的逃跑路线可以被看作是在 $n$ 个岛屿上，这些岛屿由 $n-1$ 条航线两两相连。 每个岛上都有足够的补给。**假设他每在海上航行一天，就要花费一个单位的食物**。黑心老板规定，**能装 $k$ 单位的食物的背包将会卖 $k$ 万元**。 PF 可以命令在任意两个**通过时间不超过 $d$**，**并且岛 $v$ 到岛 $u$ 的航线上至少有 $q$ 个岛屿**（**不包括 $u$ 和 $v$**）的岛屿 $u$ 与 $v$ 之间建立一条双向航线，通过这条航线的时间为 $\left\lfloor \dfrac{time(u \to v)}{2}\right\rfloor$。由于经济问题，**他只能建造一条额外的航线**。 小 E 可以根据官方给出的航线（**包括新增的航线**）确认 PF 到每个岛上的**最短时间**。 PF 将会在 $t$ 时发现小 E 逃走并开始追击。 为了节省钱，同时逃脱 PF 的追捕，小 E 想请你帮他编一个程序，计算最小的 $k$，使得他能够顺利逃脱到至少 $l$ 个岛屿。 **补给不需要时间，中途抓住也算抓住，同时到达则不算。** **在岛屿上进行补给不需要时间，可以无限进行补给，只要背包装得下。** 题意概括： 有两个人 $a$，$b$ 和一颗 $n$ 个节点组成的树，$a$ 比 $b$早出发 $t$ 秒。如果两个节点之间通过时间不超过 $d$ 则 $b$ 可以在这两点之间建一条通过时间为 $\left\lfloor \dfrac{time(u \to v)}{2}\right\rfloor$ 的线路，求一个方案使 $a$ 至少到 $l$ 个点的最短时间不比 $b$ 长，并在此基础下要求岛屿之间距离最大值尽量小。

无

无

【样例解释】 样例 $1$：  对于样例 $1$，最后能到的点为 $1,2,4,5$，最小花费为 $7$。由于狱长 PF 从点 $3\to 5$ 要经过点为 $5\to1\to2\to3$，满足中间的点数 $\ge q$，故狱长 PF 可以连边点 $3$ 和点 $5$。如果狱长 PF 选择连边 $5\to3$，那么到点 $3$ 的时间为 $3+1+ \left\lfloor \dfrac{1+5+5}{2}\right\rfloor = 9$。而小 E 到点 $3$ 的最短时间为 $5 + 5 = 10$，不满足条件，故无论 $k$ 的大小，点 $3$ 都是不可到达的。 ------------ 【数据范围】 | 测试点编号 | $n\le$ | $t\le$ | $p_i,e_i\le$ | $d\le$ | 时间限制| 空间限制 |特点| | :----------: | :----------: | :----------: | :----------: | :----------: |:-----: | :----------: |:----------: | |$1$ | $10$ | $50$ | $50$ | $50$ |$1s$ | $128M$ |加边操作 不影响答案| |$2$ | $16$ | $50$ | $50$ | $50$ |$1s$ | $128M$ |无| | $3,4$ | $500$ | ${500}$ | ${500}$ |$500$ | $1s$ | $128M$ |加边操作 不影响答案| | $5$ | $500$ | ${500}$ | ${500}$ |${500}$ | $1s$ | $128M$ |$q = 0$| | $6,7$ | $500$ | ${500}$ | ${500}$ |${500}$ | $1s$ | $128M$ |无| | $8$ | $\small{2.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $1s$ | $128M$ |加边操作 不影响答案| | $9,10$ | $\small{2.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $1s$ | $128M$ |$q = 0$| | $11 \sim 14$ | $\small{2.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $1s$ | $128M$ |无| | $15$ | $\small{2.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $1s$ | $256M$ |无| | $16$ | $\small{7.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $2s$ | $256M$ |无| | $17$ | $\small{7.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $1s$ | $256M$ |无| | $18 \sim 20$ | $\small{7.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $3s$ |$512M$ |无| 对于 $100 \%$ 的数据，$n\le 7.5\times 10^3$，$1\le l\le n$，$0\le t \le 10^8$，$0 \le u_i