【点分治练习】boatherds

2015年1月10日1,1120

【问题描述】

询问一颗树上距离为 K 的点对是否存在

【输入格式】

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

【输出格式】

对于每个 K 每行输出一个答案

存在输出”AYE”, 否则输出”NYE”(不包含引号)

【样例输入】

2 2

1 2 1

1

2

【样例输出】

AYE

NYE

【数据规模与约定】

对于 30% 的数据,有 1 ≤ n ≤ 100

对于 60% 的数据,有 1 ≤ n ≤ 10^3 1 ≤ m ≤ 50

对于100%的数据,有1≤n≤10^4,1≤m≤100,1≤c≤1000,1≤K≤10^7

【题解】

czy神犇良心出题照顾蒟蒻

点分治的时候暴力枚举一下a_i,在set中查询
复杂度O(nmlogn^2)