【模板】点分治1

题目背景

感谢 hzwer 的点分治互测。

题目描述

给定一棵有 $n$ 个点的树。 询问树上距离为 $k$ 的点对是否存在。

输入输出格式

输入格式


第一行两个数 $n,m$。 接下来 $n-1$ 条边 $a,b,c$ 描述 $a$ 到 $b$ 有一条长度为 $c$ 的路径。 接下来 $m$ 行每行询问一个 $K$。

输出格式


对于每个 $K$ 每行输出一个答案,存在输出 `AYE`,否则输出 `NAY`。

输入输出样例

输入样例 #1

2 1
1 2 2
2

输出样例 #1

AYE

说明

对于 $30\%$ 的数据,$n\leq 100$。 对于 $60\%$ 的数据,$n\leq 1000$,$m\leq 50$ 。 对于 $100\%$ 的数据,$n\leq 10^4$,$m\leq 100$,$c\leq 10^4$,$K\leq 10^7$。