405004: GYM101736 D Dessert First Strategy

Dessert First Strategy (DFS) refers to the strategy to monopolize the dessert before other people have a chance to get to it. This usually involves an elaborate plan with various positions that should be occupied by units.

More precisely, there are n positions that form a tree. Each position is one of k roles, labeled from 1 to k inclusive. You have an unlimited number of each of the two available types of units (tourist and cactus) to assign to the positions. However, you must assign the same unit within each role. That is, if you assign a tourist to a position of role 1, then you cannot assign a cactus to another position of role 1.

Each of the two units has a list of valid roles they can take (for example, cacti cannot take the role that is messenger pigeon). It is guaranteed that each role can be taken by at least one of the two units. Now, it is always possible to assign units to positions based on the aforementioned restrictions.

The n positions form a tree, and each edge has an effectiveness value c_i. This effectiveness can be gained if the two units assigned to the positions adjacent to the edge are the same type, in which case the effectiveness of the edge is c_i. If the two units are not the same type, then the effectiveness of the edge is 0. The effectiveness of the strategy is the sum of the effectivenesses of each edge.

Given the number of positions, the number of roles, and the shape of the tree, calculate the maximum possible effectiveness that could be obtained by assigning units to the roles optimally.

The first line of input contains four space-separated integers n, k, p, q (1 ≤ n ≤ 10⁵;1 ≤ p, q ≤ k ≤ 200), representing the number of positions, the number of communications, and the number of roles respectively.

The second line of input contains p distinct space-separated integers each between 1 and k inclusive, representing the roles that the tourists can take.

The third line of input contains q distinct space-separated integers each between 1 and k inclusive, representing the roles that the cacti can take.

The fourth line contains n space-separated integers. The ith integer r_i represents the role of the ith position.

Each of the next n - 1 lines contains three space-separated integers a_i, b_i, and c_i (1 ≤ a < b ≤ n;1 ≤ c_i ≤ 10⁴), describing the ith edge that is between positions a_i and b_i with a possible effectiveness gain of c_i.

Output a single integer representing the maximum effectiveness that can be gained.

5 3 2 2
1 2
2 3
1 1 2 1 3
1 2 2
2 3 3
3 4 1
4 5 42

6

In the first sample, it is optimal to have the tourists take roles 1 and 2 while the cacti take role 3. This means we get the following effectiveness gains:

• 2 effectiveness from 1 and 2
• 3 effectiveness from 2 and 3
• 1 effectiveness from 3 and 4