宝藏 - 题目

A 国有 $n$ 个岛屿，由 $m$ 条桥（无向边）连接。通过这些桥，你可以从任意一个岛屿到达其他任何岛屿。

每个岛屿上有无限的宝藏，但同一岛屿上的宝藏具有相同的属性和价值。每种属性的宝藏最多出现在 10 个岛屿上。

有一位勇士准备去寻找宝藏，他从 $x$ 号岛屿出发，通过桥梁到达一些岛屿（包括 $x$），并获取宝藏。但每种属性的宝藏只能获取一次，也就是说，如果勇士到达了多个拥有相同属性宝藏的岛屿，他只会选择其中一个岛屿上的宝藏进行收集。

每座桥上都有一名守卫。如果你想通过这座桥，你需要通过守卫的测试，即勇士的战斗力不能低于守卫的战斗力。

在这个问题中，A 国会发生两类事件：

$0\ x\ y$：$x$ 号岛屿上的宝藏价值增加，这意味着该岛屿上所有宝藏的价值增加 $y$。

$1\ x\ y$：一名战斗力为 $y$ 的勇士从 $x$ 号岛屿出发去寻找宝藏。他希望你计算出他总共能获得的最大价值。

第一行是一个正整数 $T(T \le 5)$，表示数据组数。

对于每组测试数据，第一行包含三个正整数 $n, m, q(1 \le n, q \le 100000, n-1 \le m \le 200000)$，分别表示 A 国的岛屿数量、桥梁数量和询问次数。

接下来一行输入 $n$ 个正整数，其中第 $i$ 个数 $c_i(1 \le c_i \le n)$ 表示第 $i$ 个岛屿上宝藏的属性。

接下来一行输入 $n$ 个正整数，其中第 $i$ 个数 $val_i(1 \le val_i \le 100000)$ 表示第 $i$ 个岛屿上宝藏的价值。

接下来 $m$ 行，每行三个正整数 $u, v, w(1 \le u, v \le n, u \neq v, 1 \le w \le 100000)$，表示连接两个岛屿 $u, v$ 的桥，其中 $w$ 表示该桥守卫的战斗力。

接下来 $q$ 行，每行三个整数 $op, x, y(0 \le op \le 1, 1 \le x \le n, 1 \le y \le 100000)$，表示一个操作：

如果 $op = 0$，表示一个事件，$x$ 号岛屿上的宝藏价值增加 $y$。

如果 $op = 1$，表示一个询问，询问战斗力为 $y$ 的勇士从 $x$ 号岛屿出发能获得的最大价值。

对于每个询问，输出一行一个正整数，表示勇士能获得的最大价值。

QOJ.ac