在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为 $1$），有以下两种操作：

1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）

2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）

你能帮帮她吗?

Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 $n$ 个城市设有业务，设这些城市分别标记为 $0$ 到 $n-1$，一共有 $m$ 种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 $k$ 种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

2018年10月25日，农历戊戌年九月十七。

猪王国的文明源远流长，博大精深。

世界树的形态可以用一个数学模型来描述：世界树中有 $n$ 个种族，种族的编号分别从 $1$ 到 $n$，分别生活在编号为 $1$ 到 $n$ 的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为 $1$。保证连接的方式会形成一棵树结构，即所有的聚居地之间可以互相到达，并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度；例如，若聚居地 $a$ 和 $b$ 之间有道路，$b$ 和 $c$ 之间有道路，因为每条道路长度为 $1$ 而且又不可能出现环，所以 $a$ 与 $c$ 之间的距离为 $2$。

出于对公平的考虑，第 $i$ 年，世界树的国王需要授权 $m_i$ 个种族的聚居地为临时议事处。对于某个种族 $x$（$x$ 为种族的编号），如果距离该种族最近的临时议事处为 $y$（$y$ 为议事处所在聚居地的编号），则种族 $x$ 将接受 $y$ 议事处的管辖（如果有多个临时议事处到该聚居地的距离一样，则 $y$ 为其中编号最小的临时议事处）。

现在国王想知道，在 $q$ 年的时间里，每一年完成授权后，当年每个临时议事处将会管理多少个种族（议事处所在的聚居地也将接受该议事处管理）。 现在这个任务交给了以智慧著称的灵长类的你：程序猿。请帮国王完成这个任务吧。

著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品—— 概率充电器：

“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！SHOI 概率充电器，您生活不可或缺的必需品！能充上电吗？现在就试试看吧！”

SHOI 概率充电器由 $n-1$ 条导线连通了 $n$ 个充电元件。进行充电时，每条导 线是否可以导电以概率决定，每一个充电元件自身是否直接进行充电也由概率 决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。

作为 SHOI 公司的忠实客户，你无法抑制自己购买 SHOI 产品的冲动。在排 了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道，进入充电状态的元件个数的期望是多少呢？

L 公司有 $N$ 个工厂，由高到底分布在一座山上。工厂 $1$ 在山顶，工厂 $N$ 在山脚。

由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第 $i$ 个工厂目前已有成品 $P_i$ 件，在第 $i$ 个工厂位置建立仓库的费用是 $C_i$ 。

对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 L 公司产品的对外销售处设置在山脚的工厂 $N$ ，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送 $1$ 个单位距离的费用是 $1$ 。

假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：

• 工厂 $i$ 距离工厂 $1$ 的距离 $X_i$（其中 $X_1=0$ ）;
• 工厂 $i$ 目前已有成品数量 $P_i$ ;
• 在工厂 $i$ 建立仓库的费用 $C_i$ ;

请你帮助 L 公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。

小 R 热衷于做黑暗料理，尤其是混合果汁。

商店里有 $n$ 种果汁，编号为 $0,1,\cdots,n-1$ 。$i$ 号果汁的美味度是 $d_i$ ，每升价格为 $p_i$​ 。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，$i$ 号果汁最多只能添加 $l_i$ 升。

现在有 $m$ 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第 $j$ 个小朋友希望他得到的混合果汁总价格不大于 $g_j$ ，体积不小于 $L_j$​ 。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

在一些扑克游戏里，如德州扑克，发牌是有讲究的。一般称呼专业的发牌手为荷官。荷官在发牌前，先要销牌。所谓销牌，就是把当前在牌库顶的那一张牌移动到牌库底，它用来防止玩家猜牌而影响游戏。

假设一开始，荷官拿出了一副新牌，这副牌有 $N$ 张不同的牌，编号依次为 $1$ 到 $N$ 。由于是新牌，所以牌是按照顺序排好的，从牌库顶开始，依次为 $1, 2, \dots$ 直到$N$ ，$N$ 号牌在牌库底。为了发完所有的牌，荷官会进行$N$ 次发牌操作，在第 $i$ 次发牌之前，他会连续进行 $R_i$ 次销牌操作， $R_i$ 由输入给定。请问最后玩家拿到这副牌的顺序是什么样的？

给定一个 $n$ 个点，以 $1$ 为根的有根树，砍断第 $i$ 条边的代价为 $c_i$。有 $m$ 次询问，每次给出 $k_i$ 个关键点（保证关键点不含 $1$ 号节点），询问能够使 $1$ 号节点不能到达任何关键点，所要砍断边的代价和最小是多少。

数据范围：$n,m \leq 250000,\sum {k_i} \leq 5 \times 10^5$