题解 P3806 【【模板】点分治1】（待填坑）
pantw
2018-01-22 00:03:36
借鉴了题解区的写法。
```cpp
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 10010
#define maxm 20010
#define INF 0x3F3F3F3F
using namespace std;
inline int r() {
char c = getchar();
int x = 0;
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = 10 * x + c - '0', c = getchar();
return x;
}
inline int max(int a, int b) {
return a > b ? a : b;
}
int n, m, k[107];
int head[maxn], nxt[maxm], to[maxm], weight[maxm], ec;
int que[maxn], tou, dis[maxn];
int siz[maxn], sum, root, rtson;
bool vis[maxn], ans[maxn];
void add(int u, int v, int w) {
nxt[++ec] = head[u];
head[u] = ec;
weight[ec] = w;
to[ec] = v;
}
void getroot(int x, int fa) {
int son = 0; siz[x] = 1;
for(int e = head[x]; e; e = nxt[e]) if(to[e] != fa && !vis[to[e]]) getroot(to[e], x), siz[x] += siz[to[e]], son = max(son, siz[to[e]]);
if((son = max(son, sum - siz[x])) < rtson) root = x, rtson = son;
}
void dfs(int x, int fa) {
que[tou++] = dis[x];
for(int e = head[x]; e; e = nxt[e]) if(to[e] != fa && !vis[to[e]]) dis[to[e]] = dis[x] + weight[e], dfs(to[e], x);
}
set<int> S;
void query(int x) {
for(int i = 1; i <= m; i++) if(!ans[i]) ans[i] = *S.lower_bound(k[i] - x) == k[i] - x;
}
void solve(int x) {
S.clear(); vis[x] = true; S.insert(0);
for(int e = head[x]; e; e = nxt[e]) {
if(!vis[to[e]]) {
tou = 0; dis[to[e]] = weight[e]; dfs(to[e], 0);
for(int i = 0; i < tou; i++) query(que[i]);
for(int i = 0; i < tou; i++) S.insert(que[i]);
}
}
for(int e = head[x]; e; e = nxt[e]) {
if(!vis[to[e]]) {
rtson = sum = siz[to[e]];
getroot(to[e], 0);
solve(to[e]);
}
}
}
int main() {
n = r(); m = r();
for(int i = 1; i < n; i++) {
int u, v, w;
u = r(), v = r(), w = r();
add(u, v, w);
add(v, u, w);
}
for(int i = 1; i <= m; i++) k[i] = r();
rtson = sum = n, getroot(1, 0), solve(root);
for(int i = 1; i <= m; i++) puts(ans[i] ? "AYE" : "NAY");
return 0;
}
```