Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Chow, Mo

By reborn · Limits 1s, 256 MB

Mo, the jumper has found an extraordinary tree in the woods. He absolutely loves it. He already has made quite a few jumps from one branch to another. After a while, being bored, he wonders what would be the minimum time to reach a vertex from another.

Formally, a tree is a connected graph with bidirectional edges and there exists only one path between two vertices. The tree Mo found is rooted at 11 and has NN vertices numbered from 11 to NN. Every vertex ii has some color cic_i. It takes him dd seconds to go from vertex uu to vv if u, vu, ~v are adjacent. Also, Mo can jump from a vertex uu to vertex vv if the colors of those two vertices are same, i.e. cu=cvc_u = c_v. These jumps take him fcuf_{c_u} seconds.

For two vertices ss and tt, find out the minimum time needed for Mo to reach tt from ss.

Input

First line contains an integer TT.

There are TT test cases. For each test case ---

  • First line contains two integers N, dN, ~d, giving the number of vertices in the tree and the time needed to move between adjacent vertices. The vertices are numbered from 11 to NN.
  • Next line follows with N1N-1 integers, the iith of which denotes the parent of vertex i+1i+1.
  • The next line contains NN integers, the iith integer denotes the color of vertex ii, cic_i.
  • The following line contains another NN integers, the iith integer denotes fcif_{c_i}. It is guaranteed that for any i, ji, ~j, if ci=cjc_i = c_j then fci=fcjf_{c_i} = f_{c_j}.
  • The last line contains two integers ss and tt, the source and the destination.

Scoring

Subtask 1 (20 points):

  • 1T51 \leq T \leq 5,
  • 2N1032 \leq N \leq 10^3,
  • 1ci,s,tN1 \leq c_i, s, t \leq N,
  • 0d,fci1040 \leq d, f_{c_i} \leq 10^4.

Subtask 2 (30 points):

  • 1T101 \leq T \leq 10,
  • 2N1052 \leq N \leq 10^5,
  • 1ci,s,tN1 \leq c_i, s, t \leq N,
  • 0d,fci1070 \leq d, f_{c_i} \leq 10^7,
  • d=fcid = f_{c_i} for every cic_i.

Subtask 3 (50 points):

  • 1T101 \leq T \leq 10,
  • 2N1052 \leq N \leq 10^5,
  • 1ci,s,tN1 \leq c_i, s, t \leq N,
  • 0d,fci1070 \leq d, f_{c_i} \leq 10^7.

Output

For each test case, output the minimum time needed in seconds to reach tt from ss.

Sample

InputOutput
1
8 10
1 2 2 4 4 1 6
3 2 4 4 3 2 1 4
12 20 14 14 12 20 5 14
7 8
44

Mo walks 7-1 in d=10 seconds. 1-2 in another 10 seconds. Then he goes to 3 via 2-3 causing another 10 seconds. Then he jumps from vertex-3 to vertex-8 since they are the same color. This jump takes him 14 seconds. Total time: 44 seconds.


Large input file. Please use faster I/O. (e.g. scanf(), printf() in C/C++)

Discussion

Toph uses cookies. By continuing you agree to our Cookie Policy.