点分治解析

点分治是一种处理树上路径的方法，诸如询问树上长度为k的路径是否存再等问题。

对于这类问题，如果给定起点和终点让我们求路径长度，显然用LCA就好。但有些题目没有给定的起点和终点，如果强行使用LCA，就会得到O(n^2logn)的时间复杂度。当然，这时候也可以直接挨个点暴力DFS遍历，那样也会得到O(n^2)的时间复杂度。

想要得到更优的时间复杂度，就要用到点分治。点分治和直接暴力遍历的最大区别就是：不遍历所有点，而是遍历重心。重心有一个性质，以树的重心为根时，所有子树的大小都不超过树的大小的一半。由此，就可以对时间复杂度进行优化，达到O(nlogn)。接下来，就来思考如和通过重心来遍历。

首先我们要知道如何求重心，代码如下

void getroot(int u, int f) {siz[u] = 1, maxv[u] = 0;
//maxv[u]必须更新为0，因为要求多次重心for (const auto& [v, w] : g[u]) {if (vis[v] || v == f)continue;getroot(v, u);siz[u] += siz[v];maxv[u] = max(maxv[u], siz[v]);}maxv[u] = max(maxv[u], sum - siz[u]);
//使用sum并更新以正确限制范围if (maxv[u] < maxv[root])root = u;
}

另外，还需要从重心开始遍历，得到其子树中所有节点到重心的距离，代码如下

void getdis(int u, int f, int d) {if (d > NK)return;//NK之后解释dis.push_back(d);//dis存，之后会清空for (const auto& [v, w] : g[u]) {if (vis[v] || v == f)continue;getdis(v, u, d + w);}
}

有了些前置处理后，当K的上限比较小时，我们可以用桶来存路径的长度，当两段路径到一个点的路径之和等于所需值时即可，这也是该算法的关键。详细见代码。

模板题链接https://www.luogu.com.cn/problem/P3806

///P3806  点分治模板  k较小可以用桶优化 复杂度为o(nlogn)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 0x3f3f3f3f;
const int N = 1e4 + 10;
const int NK = 1e7 + 10;
//NK为K的最大值，可以优化代码，防止产生错误
vector<pair<int, int>>g[N];
bool vis[N], cnt[NK], ans[N];//vis数组防止重复查找重心
//cnt是桶，ans用来离线处理答案
int n, m, sum, root;
vector<int>dis, q;
int siz[N], maxv[N];//求重心数组void getroot(int u, int f) {siz[u] = 1, maxv[u] = 0;for (const auto& [v, w] : g[u]) {if (vis[v] || v == f)continue;getroot(v, u);siz[u] += siz[v];maxv[u] = max(maxv[u], siz[v]);}maxv[u] = max(maxv[u], sum - siz[u]);if (maxv[u] < maxv[root])root = u;
}void getdis(int u, int f, int d) {if (d > NK)return;dis.push_back(d);for (const auto& [v, w] : g[u]) {if (vis[v] || v == f)continue;getdis(v, u, d + w);}
}void calc(int u) {vector<int>tot;//tot数组用来清空桶，如果不用tot数组，就要一次清理1e7的数据cnt[0] = 1;//一定要将0标记上for (const auto& [v, w] : g[u]) {if (vis[v])continue;dis.clear();getdis(v, u, w);for (int i = 0; i < m; i++) {if (ans[i])continue;//离线做法for (int d : dis) {if (d > q[i])continue;//显然不可能if (cnt[q[i] - d]) {ans[i] = 1;break;}}}//更新桶for (int d : dis) {if (d > NK || cnt[d])continue;cnt[d] = 1;tot.push_back(d);}}//清空桶for (int d : tot) {cnt[d] = 0;}
}void work(int u) {//logn的由来 不断寻找重心，从重心开始遍历vis[u] = 1;calc(u);for (const auto& [v, w] : g[u]) {if (vis[v])continue;sum = siz[v];root = 0, maxv[root] = INF;getroot(v, 0);work(root);}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cin >> n >> m;for (int i = 1; i < n; i++) {int u, v, w;cin >> u >> v >> w;g[v].emplace_back(u, w);g[u].emplace_back(v, w);}q.resize(m);for (int i = 0; i < m; i++) {cin >> q[i];}sum = n;root = 0, maxv[root] = INF;getroot(1, 0);work(root);for (int i = 0; i < m; i++) {cout << (ans[i] ? "AYE" : "NAY") << endl;}return 0;
}