P17785 上伊那牡丹不是罪过

『可不可以，不再当朋友了？』 『——那就不再当朋友了。』

牡丹和伊吹买了一套神奇的酒具，你可以将它视作一棵以 $1$ 为根，大小为 $n$ 的树，每个点上都可以存一些酒，初始均为空。 有 $k$ 个可以加酒的地方，被称为特殊点。其中第 $i$ 个特殊点是点 $t_i$。 接下来发生了 $m$ 件事： - `1 u v`，牡丹会喝掉从 $u$ 点到 $v$ 点的路径上的每个点的酒，神奇地，这些点上的酒量**不会**因此减少，牡丹喝掉的酒量为路径上点酒量和。 - `2 w`，伊吹需要从 $k$ 个特殊点中选择一个点，让选出的点的子树中的每个点的酒量增加 $w$。 伊吹好奇求出在最优操作策略下牡丹喝掉的酒量的最小值。注意伊吹决策时已知全部操作。 ### 实现细节 本题是一道**函数式交互题**。选手不需要，也不应该实现 `main` 函数，并且不应当向 stdin、stdout 中读入或输出任何字符，否则将视作作弊处理。相应地，选手需要在程序中实现以下函数： ```cpp __int128 botan(const int &n,const std::vector &SpIds,const std::vector &G,const std::vector &Ops); ``` `n` 的含义见题目描述。 `SpIds` 是一个长为 $k$ 的 `int` 数组，储存 $k$ 个特殊点下标。 `G` 是一个长为 $n-1$ 的 `pair` 数组，每个对 $(x,y)$ 表示树上存在一条连接点 $x,y$ 的边。 `Ops` 是一个长为 $m$ 的 `tuple` 数组，第 $i$ 个 `tuple` 描述了第 $i$ 次操作，其中第一个元素描述了操作类型 $kd$，若 $kd=1$，第二个元素和第三个元素分别表示本次操作的 $u,v$；若 $kd=2$，第二个元素表示本次操作的 $w$，第三个元素无意义。 该函数需要返回你得到的答案。保证每组数据中该函数被调用恰好一次。

无

无

#### 【数据范围】 对于所有数据，保证： - $1 \leq n \leq 10^6$。 - $1 \leq m \leq 10^6$。 - $1 \leq k \leq n$。 - $1 \leq u_i,v_i \leq n$。 - $1 \leq w \le 10^4$。 #### 【样例说明】 在上面给定的样例输入中，第一行三个数为 $n,m,k$，第二行三个数为特殊点编号，接下来 $n-1$ 行每行两个数表示存在一条连接这两个点的树边，接下来 $m$ 行每行输入一个操作，格式与题目描述中给出的一致。输出的就是答案。 --- *原来自始至终做好准备的，就只有我吗。*