#P17785. 上伊那牡丹不是罪过
上伊那牡丹不是罪过
背景
『可不可以,不再当朋友了?』
『——那就不再当朋友了。』
题目描述
牡丹和伊吹买了一套神奇的酒具,你可以将它视作一棵以 为根,大小为 的树,每个点上都可以存一些酒,初始均为空。
有 个可以加酒的地方,被称为特殊点。其中第 个特殊点是点 。
接下来发生了 件事:
-
1 u v,牡丹会喝掉从 点到 点的路径上的每个点的酒,神奇地,这些点上的酒量不会因此减少,牡丹喝掉的酒量为路径上点酒量和。 -
2 w,伊吹需要从 个特殊点中选择一个点,让选出的点的子树中的每个点的酒量增加 。
伊吹好奇求出在最优操作策略下牡丹喝掉的酒量的最小值。注意伊吹决策时已知全部操作。
实现细节
本题是一道函数式交互题。选手不需要,也不应该实现 main 函数,并且不应当向 stdin、stdout 中读入或输出任何字符,否则将视作作弊处理。相应地,选手需要在程序中实现以下函数:
__int128 botan(const int &n,const std::vector<int> &SpIds,const std::vector<std::pair<int,int>> &G,const std::vector<std::tuple<int,int,int>> &Ops);
n 的含义见题目描述。
SpIds 是一个长为 的 int 数组,储存 个特殊点下标。
G 是一个长为 的 pair 数组,每个对 表示树上存在一条连接点 的边。
Ops 是一个长为 的 tuple 数组,第 个 tuple 描述了第 次操作,其中第一个元素描述了操作类型 ,若 ,第二个元素和第三个元素分别表示本次操作的 ;若 ,第二个元素表示本次操作的 ,第三个元素无意义。
该函数需要返回你得到的答案。保证每组数据中该函数被调用恰好一次。
输入格式
无
输出格式
无
5 10 3
1 3 5
1 2
2 3
2 4
3 5
2 3
1 1 5
2 10
1 4 5
2 3
1 2 3
2 7
1 3 5
1 1 4
1 2 4
39
提示
【数据范围】
对于所有数据,保证:
-
。
-
。
-
。
-
。
-
。
【样例说明】
在上面给定的样例输入中,第一行三个数为 ,第二行三个数为特殊点编号,接下来 行每行两个数表示存在一条连接这两个点的树边,接下来 行每行输入一个操作,格式与题目描述中给出的一致。输出的就是答案。
原来自始至终做好准备的,就只有我吗。