Description

Given a tree with $n$ nodes, determine for each query whether there exists a pair of nodes whose distance on the tree equals $k$.

Input Format

The first line contains two integers $n, m$.

The next $n-1$ lines, each contains three integers $u, v, w$, representing an edge between $u$ and $v$ with weight $w$.

Then $m$ lines follow, each containing one integer $k$, representing a query.

Output Format

For each query, output one line with a string representing the answer. Output AYE if such a pair exists, otherwise output NAY.

2 1
1 2 2
2

AYE

Hint

Constraints

• For $30\%$ of the testdata, $n \leq 100$ is guaranteed.
• For $60\%$ of the testdata, $n \leq 1000$, $m \leq 50$ are guaranteed.
• For $100\%$ of the testdata, $1 \leq n \leq 10^4$, $1 \leq m \leq 100$, $1 \leq k \leq 10^7$, $1 \leq u, v \leq n$, $1 \leq w \leq 10^4$ are guaranteed.

Notes

• This problem does not stress constant factors.
• If test point #7 keeps RE/TLE, consider checking this post: https://www.luogu.com.cn/discuss/show/188596.

Translated by ChatGPT 5