33OJ
登录 注册

#P17785. 上伊那牡丹不是罪过

    ID: 20372 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度提高+/省选− 上传者: 标签>线段树交互题O2优化优先队列最近公共祖先 LCA离线处理

上伊那牡丹不是罪过

背景

『可不可以,不再当朋友了?』

『——那就不再当朋友了。』

题目描述

牡丹和伊吹买了一套神奇的酒具,你可以将它视作一棵以 11 为根,大小为 nn 的树,每个点上都可以存一些酒,初始均为空。

有 kk 个可以加酒的地方,被称为特殊点。其中第 ii 个特殊点是点 tit_i。

接下来发生了 mm 件事:

  • 1 u v,牡丹会喝掉从 uu 点到 vv 点的路径上的每个点的酒,神奇地,这些点上的酒量不会因此减少,牡丹喝掉的酒量为路径上点酒量和。

  • 2 w,伊吹需要从 kk 个特殊点中选择一个点,让选出的点的子树中的每个点的酒量增加 ww。

伊吹好奇求出在最优操作策略下牡丹喝掉的酒量的最小值。注意伊吹决策时已知全部操作。

实现细节

本题是一道函数式交互题。选手不需要,也不应该实现 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 是一个长为 kk 的 int 数组,储存 kk 个特殊点下标。

G 是一个长为 n−1n-1 的 pair 数组,每个对 (x,y)(x,y) 表示树上存在一条连接点 x,yx,y 的边。

Ops 是一个长为 mm 的 tuple 数组,第 ii 个 tuple 描述了第 ii 次操作,其中第一个元素描述了操作类型 kdkd,若 kd=1kd=1,第二个元素和第三个元素分别表示本次操作的 u,vu,v;若 kd=2kd=2,第二个元素表示本次操作的 ww,第三个元素无意义。

该函数需要返回你得到的答案。保证每组数据中该函数被调用恰好一次。

输入格式

无

输出格式

无

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

提示

【数据范围】

对于所有数据,保证:

  • 1≤n≤1061 \leq n \leq 10^6。

  • 1≤m≤1061 \leq m \leq 10^6。

  • 1≤k≤n1 \leq k \leq n。

  • 1≤ui,vi≤n1 \leq u_i,v_i \leq n。

  • 1≤w≤1041 \leq w \le 10^4。

【样例说明】

在上面给定的样例输入中,第一行三个数为 n,m,kn,m,k,第二行三个数为特殊点编号,接下来 n−1n-1 行每行两个数表示存在一条连接这两个点的树边,接下来 mm 行每行输入一个操作,格式与题目描述中给出的一致。输出的就是答案。


原来自始至终做好准备的,就只有我吗。