#P1460. [模板题][点分治]Pku2114 Boatherds

    ID: 472 传统题 1000ms 512MiB 尝试: 347 已通过: 60 难度: 6 上传者: 标签>CF2000提高+/省选-点分治点分治容斥去重相向双指针难度分类

[模板题][点分治]Pku2114 Boatherds

题目描述

给你一棵 nn 个点的带权有根树,有 pp 个询问,每次询问树中是否存在一条长度为 LenLen 的路径,如果是,输出 Yes 否输出 No.

输入格式

第一行两个整数 n,pn, p 分别表示点的个数和询问的个数. 接下来n-1行每行三个数 x,y,cx, y, c,表示有一条树边 x→yx\to y,长度为c. 接下来 pp 行每行一个数 LenLen,表示询问树中是否存在一条长度为 LenLen 的路径.

输出格式

输出有 pp 行,Yes 或 No.

6 4 
1 2 5 
1 3 7 
1 4 1 
3 5 2 
3 6 3 
1 
8 
13 
14
Yes 
Yes 
No 
Yes 

提示

【数据范围】

30%的数据,n≤100.n≤100.

100%的数据,n≤10000,p≤100,n≤10000,p≤100,长度≤100000≤100000.