P16352 「Gensokyo OI Round 1」雨后长虹

::::info[引言：其之四] :::align{center} $\textbf{旧忆再染新绪，\color{gold}幻梦}\textbf{长存。}$ ::: :::: 门扉缓缓打开，一线天光洒入。 ——门外的晴空，湛蓝一片。 不知何时，雨已经停了。 博丽的巫女，从秘神的国度中轻巧地跃出，在蓝天下自由地翱翔。 忽然间，她像察觉到了什么似的，在半空中来了一个急刹车。常伴其身的四枚阴阳玉，也顺从着主人的意愿放缓了速度。 紧接着—— 一道隙间绽裂，老谋深算的贤者手执阳伞飘出； 一扇门扉张开，玩世不恭的贤者环抱双臂跳出； 一只巨鹰飞过，和蔼温柔的贤者背着双手走出。 “畜生界，月之都，消失的所有权……”最像妖怪的妖怪如是说； “……异变的起始，异变的结局，相较于过往愈发沉重。”绝对的究极秘神如是说； “——一直以来辛苦了，灵梦。”独臂有角的仙人如是说。 “还记得过去的那些，轻松愉快的异变吗？” “为了挡住太阳而发动的异变，为了赏樱而发动的异变，每六十年一次自然而然地发动的异变。” “那些胡闹一般的、孩子气的异变。” “那样的感觉，有多久没有体验过了？” “那些宴会上的觥筹交错，新的朋友与新的去处？” “灵梦，你难道不怀念过去那无忧无虑的时光吗？” “我们为你准备了一个惊喜。” “我们为你准备了一个惊喜。” “我们为你准备了一个惊喜。” ——三位贤者异口同声。 “一个小小的奇迹。”八云紫打开了折扇。 “一方小小的天地。”摩多罗·隐岐奈倚着背后的门。 “我们就在这里，望你来，伴你去。”茨木华扇右臂的绷带散落了，其下空无一物。 “在这众神眷恋的幻想乡中……” “在这永不终结的幻梦中……” “谜底就在你的心里。” “去痛快的玩上一场吧，正如往常一般。” “昔日的友人，幻想的住民……” “我们都在这里等你。” 一阵清风拂过，博丽灵梦不由得眨了眨眼。就在同一时刻，面前的三人同时销声匿迹——再一次。 然而，明明失去了踪影，贤者们的声音，仍然清晰可辨。 “我亲爱的灵梦哟……” “顺着记忆的河流往回走吧……” “……去回想，那命名决斗法案的理念，那符卡规则的初衷——” $$\textbf{\color{purple}“其一，妖怪能轻松发动异变。”}$$ $$\textbf{\color{orange}“其二，人类能轻松解决异变。”}$$ $$\textbf{\color{pink}“其三，否定完全的实力主义。”}$$ ——话语戛然而止。 最后的空缺，异变的谜底，留给了博丽灵梦自己。 于是，乐园的巫女，望向万里无云的天空，望向天边垂吊的彩虹。 ……她早已知晓答案。 $$\textbf{\color{red}“其四，没有东西能胜过美丽与思念。”}$$ “……紫，摩多罗，华扇……” “……啊啊。” “真的，万分感谢。” 仰头望天，回予一个淡然的微笑。

#### 原始题面 在与三位贤者交谈时，博丽灵梦得知，自己身处茨木华扇临时制造的仙界中。 与此同时，三位贤者还与过去历次异变的黑幕们商定，将她们也请进了这片仙界。 当然，为了最大程度的保留惊喜感，这些幕后的商谈都是背着各位异变解决者们——尤其是博丽巫女——进行的。 贤者们的目的是，人为地制造一场异变，借此机会让幻想乡中的大家体会到同过去一样的单纯的欢乐；同时，也有着“让近期接连参与了多项危及幻想乡的大事件的异变解决者们，得以拥有休憩的余暇”的意图。 “也就是说，果然还是要打弹幕战才能玩个尽兴，这样的考量吗。” 灵梦耸了耸肩——谁会不喜欢来上一场刺激、欢乐而又兼具美感的弹幕战呢？ 于是，巫女猛地加速，向着雨后初晴的天空飞去。 放眼望去，这片仙界中有着 $n$ 个令博丽灵梦感到可疑的区域，$m$ 条道路将这些区域连在了一起。 灵梦觉得这些地方可疑，并不是没有原因的——如果观察的仔细一点就会发现，每一处被她重点关注的区域，都能发现些许人影。粗略估计一下人数的话，每片区域大概有 $a_i$ 个人吧。 做完了基本的信息统计之后，乐园的巫女就要开始活动了。在接下来的 $t$ 个时刻中，她会进行如下三种行动： - 锁定 $q$ 个区域，并尝试通过攻占与之不同的另一个区域来使得这 $q$ 个区域之间不能连通。灵梦想要知道，她所攻占的区域中最少的人数。如果不存在这样的区域，回答 `-1`。 - 锁定 $q$ 个区域，并尝试通过攻占与之不同的另一个区域来使得这 $q$ 个区域之间不能连通。灵梦想要知道，所有可能被她当做目标的区域的人数之和。如果不存在这样的区域，回答 `-1`。 - 博丽灵梦观察到，某一片区域的人数发生了变动（有些人凭空多出来/消失掉了，似乎是在幻想乡与这个小仙界间来来往往）。 当然，前两种行动彼此之间是独立的（被攻占的区域的人们会在博丽灵梦离开后回到这里）。 #### 形式化题意 有一张 $n$ 个点，$m$ 条边的无向**连通图**，点有点权。 接下来有 $t$ 个事件发生，每个事件是以下三个中的一个： - 给定 $q$ 个关键点，你需要删掉一个非关键点使得 $q$ 个关键点之间不连通。问删除的这个点的点权最小是多少。如果不存在这样的点，回答 `-1`。 - 给定 $q$ 个关键点，你需要删掉一个非关键点使得 $q$ 个关键点之间不连通。问所有可以删除的点的点权之和。如果不存在这样的点，回答 `-1`。 - 改变某个点的点权。 询问之间互相独立，询问不改变图的结构。 > 一张图的给定若干个点之间不连通，当且仅当给定的某两个点之间不存在路径。

输入的第一行有两个整数 $n,m$，表示区域个数与道路条数。 第二行有 $n$ 个整数 $a_i$，表示第 $i$ 个区域原有的人数。 接下来 $m$ 行，每行两个整数 $x,y$，代表第 $x$ 个区域和第 $y$ 个区域之间存在道路。 第 $m+3$ 行一个整数 $t$，表示灵梦的行动次数。 接下来 $t$ 行，每行第一个整数 $opt$ 表示行动类型。 若 $opt=1$ 或 $opt=2$，接下来输入一个数 $q$，再接下来输入 $q$ 个数 $d_i$，表示被灵梦锁定的 $q$ 个点。 若 $opt=3$，接下来输入两个数 $u,k$，表示第 $u$ 个区域的人数变为了 $k$。

对于每一次 $opt=1$ 或 $opt=2$ 的行动，输出一行一个数，表示本次行动对应的答案。 特别地，如果对于某一次行动，满足条件的区域不存在，那么输出 `-1` 即可。

### 数据范围 **本题采用捆绑测试。** - Subtask $1$（$15\ \text{pts}$）：$1 \le n,m,t \le 100$，保证所有 $opt=1$ 或 $opt=2$ 的行动 的 $q$ 之和不超过 $100$。 - Subtask $2$（$15\ \text{pts}$）：$1 \le n,m,t \le 1000$。保证所有 $opt=1$ 或 $opt=2$ 的行动 的 $q$ 之和不超过 $1000$。 - Subtask $3$（$15\ \text{pts}$）：$1 \le n,m,t \le 50000$，$m=n-1$，且每个区域连接的道路数量不超过 $2$ 条。 - Subtask $4$（$15\ \text{pts}$）：$1 \le n,m,t \le 50000$，$m=n-1$。 - Subtask $5$（$20\ \text{pts}$）：$1 \le n,m,t \le 50000$。 - Subtask $6$（$20\ \text{pts}$）：无特殊限制。 对于所有数据： - $1 \le n \le 10^5$。 - $n-1 \le m \le 2 \times 10^5$。 - 保证任何一个区域可以通过若干条道路到达其他任何一个区域。 - $1 \le a_i \le 10^5$。 - $1 \le t \le 10^5$。 - 对于 $opt=1$ 或 $opt=2$ 的行动，$1 \le q \le n$，$1 \le d_i \le n$，保证所有 $opt=1$ 或 $opt=2$ 的行动 的 $q$ 之和不超过 $2 \times 10^5$。 - 对于 $opt=3$ 的行动，$1 \le u \le n$，$1 \le k \le 10^5$。