B. Error of 2
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a weighted, undirected tree of $$$N$$$ nodes. $$$d(u,v)$$$ is defined as the minimum sum of weights of the edges that lie on the unique, simple path between nodes $$$u$$$ and $$$v$$$ on the tree.

You need to answer $$$Q$$$ queries. In each query, you are given an integer $$$K$$$. Determine if there exists a pair of nodes $$$(u,v)$$$ that satisfy the following conditions:

  • $$$1 \leq u,v \leq N$$$
  • $$$K \leq d(u,v) \leq 2 \cdot K$$$

There are multiple test cases in each file, and thus you will be given an input parameter $$$T$$$, denoting that you have to solve $$$T$$$ test cases.

Input

The first line of input contains a single integer $$$T$$$ — the number of input test cases.

The first line of each test case contains two space-separated integers $$$N$$$ and $$$Q$$$ — the number of nodes in the tree and the number of queries to be answered.

The next $$$N-1$$$ lines describe the edges of the tree. The $$$i$$$-th of these $$$N-1$$$ lines contains three space-separated integers $$$u_i, v_i, w_i$$$, denoting an undirected edge between nodes $$$u_i$$$ and $$$v_i$$$ with weight $$$w_i$$$.

The next $$$Q$$$ lines describe the queries. The $$$i$$$-th of these lines contains a single integer $$$K_i$$$ — the value of $$$K$$$ for the $$$i$$$-th query.

Output

For each test case, output a binary string $$$S$$$ of length $$$Q$$$ where $$$S_i$$$ is $$$1$$$ if and only if the answer to the $$$i$$$-th query is positive, i.e. there exists a pair of nodes $$$(u, v)$$$ such that $$$K_i \le d(u, v) \le 2 \cdot K_i$$$ (and $$$S_i$$$ is $$$0$$$ otherwise).

Scoring

Constraints

It is guaranteed that

  • $$$1 \le T \le 10^4$$$
  • $$$2 \le N \le 2 \cdot 10^5$$$
  • $$$1 \le Q \le 2 \cdot 10^5$$$
  • $$$1 \le u_i, v_i \le N$$$
  • $$$1 \le w_i \le 10^{13}$$$
  • $$$1 \le K_i \le 2 \cdot 10^{18}$$$
  • The input edges forms a tree.
  • The sum of $$$N$$$ and the sum of $$$Q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Subtasks

The term Line means that the edges follow the constraint $$$u_i = i, v_i = (i + 1)$$$ for all $$$1 \le i \le N - 1$$$.

The term Star means that the edges follow the constraint $$$u_i = 1, v_i = (i + 1)$$$ for all $$$1 \le i \le N - 1$$$.

  • Subtask 1 (4 points) : $$$N \le 50, Q = 1, T \le 40$$$
  • Subtask 2 (7 points) : $$$N \le 2000$$$ and the sum of $$$N$$$ also does not exceed $$$2000$$$
  • Subtask 3 (9 points) : Line and the sum of $$$N \cdot Q$$$ does not exceed $$$2 \cdot 10^5$$$
  • Subtask 4 (16 points) : Star
  • Subtask 5 (20 points) : $$$w_i \le 20$$$
  • Subtask 6 (26 points) : Line
  • Subtask 7 (18 points) : No additional constraints
Example
Input
3
4 5
1 2 5
2 3 2
3 4 20
3
7
1
9
28
5 7
1 3 9
2 4 3
3 2 80
2 5 25
10
20
30
40
100
120
140
3 2
1 2 10000000000000
1 3 10000000000000
18000000000000
21000000000000
Output
11100
0101100
10
Note

Test Case 1 : We can find valid vertices $$$u$$$ and $$$v$$$ in the first $$$3$$$ queries in the following way:

  • Query $$$1$$$, $$$K = 3$$$ : Choose $$$u = 1$$$, $$$v = 2$$$ which has $$$d(u, v) = 5$$$. Note that $$$3 \le 5 \le 6$$$, so it is valid.
  • Query $$$2$$$, $$$K = 7$$$ : Choose $$$u = 1$$$, $$$v = 3$$$ which has $$$d(u, v) = 7$$$. Note that $$$7 \le 7 \le 14$$$, so it is valid.
  • Query $$$3$$$, $$$K = 1$$$ : Choose $$$u = 2$$$, $$$v = 3$$$ which has $$$d(u, v) = 2$$$. Note that $$$1 \le 2 \le 2$$$, so it is valid.

It can be proven that there is no valid pair $$$(u, v)$$$ for the last $$$2$$$ queries with $$$K = 9$$$ and $$$28$$$.