【模板】点分治1
题目链接：luogu P3806
题目大意
给你一棵树，路径有长度，多次询问，每次给出 k，问你是否存在路径长度为 k 的点对。
思路
这道题我们用分治的方法。
那我们假设要解决一个树，那我们先选重心作为根节点（为了减少高度节省时间）。
然后就分成两种讨论，一种是路径都在同一个子树中，那这个我们就可以把问题转换为解决这个子树。
另一种就是在两个不同的子树中（或者一个是根节点）。那我们考虑直接搜出点到根节点的距离，然后任意两个相加都是一种可行的 (k)。（因为都是在不同子树，或者是一个是根节点的话距离就是另一个到根节点的距离，所以是可以直接相加的）
首先，它可能是根节点，那它到根节点的距离就是 (0)，那一个的距离为 (0) 就是存在的。
然后你考虑枚举子树，然后求出每个点到根节点的距离。然后我们这样弄：我们枚举每个点和你给出的询问（也就是离线弄）的 (y)，那首先，这个点到根节点的距离 (x) 一定是要小于等于 (y) 的，然后如果要使得这个询问的结果是有，那距离为 (y-x) 的点是一定要存在的，因为这样就可以通过这两个，得出 (y) 的距离。
那你为了不会找到的点跟它是同一个子树中的，你就可以进行完上面的操作，才把你这个子树的距离都标记为存在。
然后你每次不同的根统计那个存在的距离都是不同的，那你就要把之前的清空。
但是不能用 memset，因为数组太大会超时。
但其实它真正有值的不多，那我们可以每次标记的时候把标记的点用一个队列记录下来（栈也行，反正就是拿个数组记录值为 (1) 的位置），然后你要清空的时候就枚举这些值为 (1) 的地方，把它们赋值为 (0) 即可。
然后加个快读什么的就可以了。
代码
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node {
int x, to, nxt;
}e[200001];
struct Tree {
int s;
}t[100001];
int n, m, x, y, z, le[100001], KK;
bool in[100001], answer[101];
int ans[10000001], rem[101], que[10000001];
int d[100001], dis[100001], root;
int k, fa[100001], S, maxn[100001];
int read() {//快读
char c = getchar();
int re = 0;
while (c < '0' || c > '9') {
c = getchar();
}
while (c >= '0' && c <= '9') {
re = re * 10 + c - '0';
c = getchar();
}
return re;
}
bool cmp(int x, int y) {
return x < y;
}
void add(int x, int y, int z) {
e[++KK] = (node){z, y, le[x]}; le[x] = KK;
}
void find_root(int now, int father) {//找重心
t[now].s = 1;
maxn[now] = 0;
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != father && !in[e[i].to]) {
find_root(e[i].to, now);
t[now].s += t[e[i].to].s;
maxn[now] = max(maxn[now], t[e[i].to].s);
}
maxn[now] = max(maxn[now], S - t[now].s);
if (maxn[now] < maxn[root]) {
root = now;
}
}
void get_dis(int now, int father) {//统计从重心到树上点的距离
d[++d[0]] = dis[now];
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != father && !in[e[i].to]) {
dis[e[i].to] = dis[now] + e[i].x;
if (dis[e[i].to] <= 10000000)//只用记录询问范围的
get_dis(e[i].to, now);
else dis[e[i].to] = -1;
}
}
void count_(int now) {//统计点对的距离
for (int i = le[now]; i; i = e[i].nxt)//直接找子树，就不用再容斥去掉第一种
if (!in[e[i].to]) {
d[0] = 0;
dis[e[i].to] = e[i].x;
get_dis(e[i].to, now);
for (int i = d[0]; i >= 1; i--)//枚举距离
for (int j = 1; j <= m; j++)//枚举询问
if (rem[j] >= d[i])//不要让数组出锅（反正你不满足这个也绝对不能得出答案）
answer[j] |= ans[rem[j] - d[i]];//看需要的另一个有没有
for (int i = 1; i <= d[0]; i++) {
que[++que[0]] = d[i];//记录哪里有值，到时清零方便省时
ans[d[i]] = 1;//记录有这样的距离
}
}
while (que[0]) {//把数组清零，如果 memset 好像会超时
ans[que[que[0]]] = 0;
que[0]--;
}
}
void dfs(int now) {//dfs 分治
ans[0] = 1;
in[now] = 1;
count_(now);
for (int i = le[now]; i; i = e[i].nxt)
if (!in[e[i].to]) {
S = t[now].s;
root = 0;
maxn[0] = n;
find_root(e[i].to, now);
dfs(root);
}
}
int main() {
n = read();
m = read();
for (int i = 1; i < n; i++) {
x = read();
y = read();
z = read();
add(x, y, z);
add(y, x, z);
}
for (int i = 1; i <= m; i++) {
rem[i] = read();
}
S = n;
maxn[0] = n;
root = 0;
find_root(1, 0);
dfs(root);
for (int i = 1; i <= m; i++) {
if (answer[i]) printf("AYE
");
else printf("NAY
");
}
return 0;
}