P3806 [Template] Centroid Decomposition

Thanks to hzwer for the centroid decomposition cross-testing.

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

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.

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

#### 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