也是点分治的简单题。（对我来说算难了orz.）
首先这里的难点就在于查询是否存在长度k。
如果我们每次都去对询问进行一次点分治，显然是过于浪费了。
所以我们可以离线做它。
在点分治过程中统计所有答案。
那么怎么统计答案，又是一大难点，如果要直接按之前找k点对的统计。
那么容斥删点的时候，需要找遍所有的组合，复杂度就到了n^2.显然不行。
这里就采用了新的思路，不再容斥。
我们对每个点是在哪个子节点的下面都做一个标记，然后再去统计即可。
如果在同一个子节点里，说明不合法。
然后对每个询问都进行一次类似二分的查询即可。
复杂度应该接近nlogn
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e4+5; const int M = 1e7+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e18 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("date1.out","w",stdout);*/} int n,m,cnt = 0,head[N],ask[105],vis[N],ssize[N],mx = INF,rt,sz = n,tot = 0,val[105]; int dis[N],a[N],b[N];//dis[i]距离i的距离,a[i]i哪个点,b[i]-i为在哪个子节点 struct Node{int to,dis,next;}e[N<<1]; inline void add(int u,int v,int w) { e[++cnt].to = v,e[cnt].dis = w,e[cnt].next = head[u],head[u] = cnt; } bool cmp(int a,int b) { return dis[a] < dis[b]; } void Findroot(int u,int fa) { ssize[u] = 1; int son = 0; for(rg int i = head[u];i;i = e[i].next) { int v = e[i].to,d = e[i].dis; if(v == fa || vis[v]) continue; Findroot(v,u); ssize[u] += ssize[v]; son = max(son,ssize[v]); } son = max(son,sz-ssize[u]); if(son < mx) mx = son,rt = u; } void Dis_slove(int u,int fa,int root,LL z) { a[++tot] = u; dis[u] = z; b[u] = root; for(rg int i = head[u];i;i = e[i].next) { int v = e[i].to,d = e[i].dis; if(v == fa || vis[v]) continue; Dis_slove(v,u,root,z+d); } } void slove(int u) { tot = 0; a[++tot] = u; dis[u] = 0; b[u] = u; for(rg int i = head[u];i;i = e[i].next) { int v = e[i].to,d = e[i].dis; if(vis[v]) continue; Dis_slove(v,u,v,d); } sort(a+1,a+tot+1,cmp); for(rg int i = 1;i <= m;++i) { if(ask[i]) continue; int L = 1,r = tot; while(L < r) { if(dis[a[L]]+dis[a[r]] > val[i]) r--; else if(dis[a[L]]+dis[a[r]] < val[i]) L++; else//长度相等 { if(b[a[L]] == b[a[r]])//如果两个点都属于同一子节点，那么关于L的查询已经结束，因为L不可能再有了,所以移动L，但是如果r-1=r，那么r-1也不用查询了，直接移动r { if(dis[a[r]] == dis[a[r-1]]) r--;// else L++; } else{ask[i] = 1;break;} } } } } void divide(int u) { slove(u); vis[u] = 1; for(rg int i = head[u];i;i = e[i].next) { int v = e[i].to,d = e[i].dis; if(vis[v]) continue; sz = ssize[v],mx = INF; Findroot(v,0); divide(rt); } } int main() { n = read(),m = read(); for(rg int i = 1;i < n;++i) { int u,v,w; u = read(),v = read(),w = read(); add(u,v,w);add(v,u,w); } for(rg int i = 1;i <= m;++i) { val[i] = read(); if(val[i] == 0) ask[i] = 1; } Findroot(1,0); divide(rt); for(rg int i = 1;i <= m;++i) printf("%s ",ask[i] ? "AYE" : "NAY"); system("pause"); return 0; }