#P3806. 【模板】点分治1

    ID: 5093 远端评测题 200ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>点分治O2优化分治深度优先搜索,DFS

【模板】点分治1

题目背景

感谢 hzwer 的点分治互测。

题目描述

给定一棵有 nn 个点的树,询问树上距离为 kk 的点对是否存在。

输入格式

第一行两个数 n,mn,m

22 到第 nn 行,每行三个整数 u,v,wu, v, w,代表树上存在一条连接 uuvv 边权为 ww 的路径。

接下来 mm 行,每行一个整数 kk,代表一次询问。

输出格式

对于每次询问输出一行一个字符串代表答案,存在输出 AYE,否则输出 NAY

2 1
1 2 2
2
AYE

提示

数据规模与约定

  • 对于 30%30\% 的数据,保证 n100n\leq 100
  • 对于 60%60\% 的数据,保证 n1000n\leq 1000m50m\leq 50
  • 对于 100%100\% 的数据,保证 1n1041 \leq n\leq 10^41m1001 \leq m\leq 1001k1071 \leq k \leq 10^71u,vn1 \leq u, v \leq n1w1041 \leq w \leq 10^4

提示

  • 本题不卡常
  • 如果您 #7 一直 RE/TLE,不妨看看 这个帖子
    请注意,第一篇题解也存在帖子中说明的问题,但是鉴于此问题与点分治算法本身无关,并且题解质量非常高,因此暂不撤下题解,仅供参考。