跪求巨佬帮助,点分治 Sub3 全 T
查看原帖
跪求巨佬帮助,点分治 Sub3 全 T
534654
zhenjianuo2025楼主2022/11/5 23:02
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10010
#define MAXM 110
#define MAXK 10000010
int n, m, tot, mxn, q[MAXM], ans[MAXM], dis[MAXN], siz[MAXN], cnt[MAXN], hvy[MAXN];
bool vis[MAXN], hvd[MAXK]; 
vector<pair<int, int> > g[MAXN];
void getdis(int u, int fa) {
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].first, w = g[u][i].second;
		if (v == fa || vis[v]) continue;
		dis[v] = dis[u] + w;
		getdis(v, u);
	} 
}
void update(int u, int fa) {
	tot++;
	for (int i = 1; i <= m; i++)
		if (q[i] >= dis[u] && q[i] - dis[u] < MAXK) ans[i] += hvd[q[i] - dis[u]];
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].first;
		if (v == fa || vis[v]) continue;
		update(v, u);
	} 
}
void add(int u, int fa) {
	siz[u] = 0, cnt[u] = 1;
	if (dis[u] < MAXK) hvd[dis[u]] = true;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].first;
		if (v == fa || vis[v]) continue;
		add(v, u);
		cnt[u] += cnt[v];
		siz[u] = max(siz[u], siz[v]);
	} 
	siz[u] = max(siz[u], tot - cnt[u]);
	if (siz[u] < siz[mxn]) mxn = u;
}
void recover(int u, int fa) {
	if (dis[u] < MAXK) hvd[dis[u]] = false; dis[u] = 0;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].first, w = g[u][i].second;
		if (v == fa || vis[v]) continue;
		recover(v, u);
	} 
}
void solve(int u) {
	vis[u] = true;
	getdis(u, 0);
	hvd[dis[u]] = true;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].first;
		if (vis[v]) continue;
		tot = mxn = 0; siz[mxn] = 1e9; update(v, u), add(v, u); hvy[i] = mxn;
	} 
	recover(u, 0);
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].first;
		if (vis[v]) continue;
		solve(hvy[i]);
	} 
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w}), g[v].push_back({u, w});
	}
	for (int i = 1; i <= m; i++) cin >> q[i];
	tot = mxn = 0; siz[mxn] = 1e9;
	update(1, 0), add(1, 0), recover(1, 0);
	solve(mxn);
	for (int i = 1; i <= m; i++) cout << (ans[i] ? "AYE" : "NAY") << "\n";
	return 0;
} 
2022/11/5 23:02
加载中...