点分治

点分治模板1

注意 vis 数组的作用 , 相当于把树切割
注意变量 sum 的作用 , 第一次写的时候没用 sum , 全部用了 n , 导致没有正确找到树的重心 , 然后 tle 了

#include <bits/stdc++.h>
using ll = long long;
const int N = 1E4 + 5 , M = 105 , O = 1E7 + 10;
const int INF = 1E9;

int n,m,rt,sum;
int sz[N],mx[N],d[N];
std::vector<std::array<int,3>> e[N];
int que[M],p[N],cnt;
bool U[O],vis[N],ans[M];
int q[N],l,r;

void Find_hs(int u,int pa) {
	
	sz[u] = 1 , mx[u] = 0;
	for (auto f : e[u]) {
		int v = f[0];
		if (v == pa || vis[v]) continue;
		Find_hs(v , u);
		sz[u] += sz[v];
		mx[u] = std::max(mx[u] , sz[v]);
	}	
	
	mx[u] = std::max(mx[u] , sum - sz[u]);
	if (mx[rt] > mx[u]) rt = u;
}
void Find_dist(int u,int pa) {
	
	p[++cnt] = d[u];
	for (auto f : e[u]) {
		int v = f[0] , w = f[1];
		if (v == pa || vis[v]) continue;
		d[v] = d[u] + w;
		Find_dist(v , u);
	}
	
}
void Dfz(int u , int pa) 
{
	vis[u] = 1 , U[0] = 1;
	l = 0 , r = -1;
	q[++r] = 0;
	
	for (auto f : e[u]) {
		
		int v = f[0] , w = f[1];
		if (v == pa || vis[v]) continue;
		
		cnt = 0;
		d[v] = w ; Find_dist(v , u);
		
		for (int i = 1 ; i <= m ; ++i) {
			for (int j = 1 ; j <= cnt ; ++j) {
				if (p[j] <= que[i]) ans[i] |= U[que[i] - p[j]];
			}
		}
		
		for (int j = 1 ; j <= cnt ; ++j) {
			if (p[j] >= O) continue;
			q[++r] = p[j] , U[p[j]] = 1;
		}
	}	
	
	//清空 U 数组 
	while (l<=r) U[q[l++]] = 0;
	
	for (auto f : e[u]) {
		int v = f[0] , w = f[1];
		if (v == pa || vis[v]) continue;
		mx[rt = 0] = INF; sum = sz[v]; 
		Find_hs(v , -1) , Find_hs(rt , -1);
		Dfz(rt , -1);
	}
	
}

int main() 
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	std::cin >> n >> m;
	for (int i = 1 ; i <= n - 1 ; ++i) {
		int u,v,w;
		std::cin >> u >> v >> w;
		e[u].push_back({v , w});
		e[v].push_back({u , w});
	}
	for (int i = 1 ; i <= m ; ++i) {
		std::cin >> que[i];
	}
	
	//注意每次的 sum 会变 
	mx[rt = 0] = INF , sum = n;
	Find_hs(1 , -1);
	Find_hs(rt , -1); //重新更新以 rt 为根的 sz 信息
	Dfz(rt , -1); 
	
	for (int i = 1 ; i <= m ; ++i) {
		if (ans[i]) std::cout << "AYE\n";
		else std::cout << "NAY\n";
	}
	
	return 0;	
}