18586번 - Salty Fish 다국어

Little Q has an apple tree with n nodes, labeled by 1, 2, . . . , n. The root of the tree is node 1, and the length of each edge is one unit. There are a_i apples on the i-th node. The price of each apple is one dollar, so if you sell t apples, you will gain t dollars.

Skywalkert, a close friend of Little Q, lost most of his money betting on programming contests, so he wants to steal some apples from this apple tree and sell them to make money.

The security system takes pictures of the nodes once per hour using m cameras. Let us denote d(x, y) as the number of edges on the shortest path from node x to node y, and denote set p(x, k) as {y | y is in subtree of x and d(x, y) ≤ k}. Note that x ∈ p(x, k). The image from the i-th camera shows the picture of all the nodes in p(x_i, k_i). If the security system detects a change in any of these images, it sounds an alarm, and the thief will be caught by Little Q.

Skywalkert is also a gifted hacker. He can lock some cameras so that images from these cameras will never change. Specifically, if he wants to lock the i-th camera, he needs to pay c_i dollars to do such a hack. Skywalkert will pay for all hacks after he steals the apples and sells them.

Please write a program to help Skywalkert earn the most money possible without being caught.

The first line of the input contains an integer T (1 ≤ T ≤ 10 000), denoting the number of test cases.

Each test case starts by a line with two integers n and m (1 ≤ n, m ≤ 300 000), denoting the number of nodes and cameras.

The second line of a test case contains n − 1 integers f₂, f₃, . . . , f_n (1 ≤ f_i < i), denoting the parents of nodes 2, 3, . . . , n.

The third line of a test case contains n integers a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁹), denoting the number of apples on nodes 1, 2, . . . , n.

Each of the next m lines of a test case contains three integers x_i, k_i, and c_i (1 ≤ x_i ≤ n, 0 ≤ k_i ≤ n, 1 ≤ c_i ≤ 10⁹), denoting the parameters of each camera.

It is guaranteed that the sum of all n is at most 10⁶, and the sum of all m is at most 10⁶.

For each test case, print a single line containing an integer denoting the maximum amount of dollars Skywalkert can earn.