Treasure

There are $n$ islands in $A$, and $m$ bridges(undirected edge) connect these $n$ islands. From any island, you can reach any other island through bridges.

There are infinite treasures on each island, but each treasure on the same island has the same property and the same value.Each property of treasure will appear on up to 10 islands.

There is a warrior who is going to hunt for treasures, starting from the $x$ island, reaching some islands(include $x$)through bridges and obtaining treasures, but treasures of each property can only be obtained once, that is, if the warrior has reached more than one islands with the same property treasures, he will only choose to collect one of the treasures in these islands.

There is a guard on each bridge. If you want to pass the bridge, you need to pass the test of the guard, that is to say, the combat power of the warrior cannot be less than that of the guard.

In this problem,two events will occur in the $A$ country:

$0\ x\ y$: Treasures on the $x$ island have increased in value, which means all treasures on this island will increase in value by $y$.

$1\ x\ y$: A warrior with combat power of $y$ sets off from the $x$ island to hunt for treasure. He wants you to figure out the most value he can get in total.

The first line of input is a positive integer $T(T\leq 5)$ representing the number of data cases.

For each test case, the first line has three positive integers $n,m,q(1\leq n,q \leq 100000,n-1\leq m\leq 200000)$, representing the number of islands in $A$ country, bridges and inquiries.

The next line inputs $n$ positive integers, and the $ith$ number $c_i(1\leq c_i\leq n)$ represents the property of the treasure on the i-th island.

The next line inputs $n$ positive integers, and the $ith$ number $val_i(1\leq val_i \leq 100000 )$ represents the value of the treasure on the i-th island.

The next $m$ line, each line of three positive integers $u,v,w(1\leq u,v\leq n,u\not=v,1\leq w\leq 100000)$ represents a bridge between two islands, $u, v$ represent the two endpoints of the bridge, $w$ represents the combat power guarded on this bridge.

The next $q$ line, each line of three integers $op, x, y(0 \leq op \leq 1,1 \leq x \leq n,1 \leq y \leq 100000)$ represents an operation:

If $op=0$, representing an event, the value of the treasure on the $x$ island increases by $y$.

If $op=1$, it represents a query, asking how much value can be obtained by a warrior with combat strength of $y$ from the $x$ island.

For each query, output a line with a positive integer representing the maximum value the warrior has earned.

1
5 4 5
1 1 1 2 2
1 2 3 1 2
1 2 1
1 4 3
2 3 1
2 5 2
1 3 1
1 3 2
0 1 5
1 3 1
1 3 2

3
5
6
8

2022“杭电杯”中国大学生算法设计超级联赛（1）

Close | Top

Administration