点分治 TLE on 10 求调
查看原帖
点分治 TLE on 10 求调
755759
zhujiangyuan楼主2024/5/21 21:25
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, NN = 2e8 +10;
int n, m, k[N], root, now, cnt;
int siz[N], d[N], f[N], dis[N], ans[N], Q[N];
bool vis[N], vis2[NN];
struct Edge { int y, v; };
vector <Edge> G[N];
void get_root (int x, int fa) {
	siz[x] = 1; f[x] = 0;
	for (auto i : G[x]) {
		int y = i.y, v = i.v;
		if (y == fa || vis[y]) continue;
		get_root (y, x);
		siz[x] += siz[y];
		f[x] = max (f[x], siz[x]);
	}
	f[x] = max (f[x], now - siz[x]);
	if (f[x] < f[root]) root = x;
}
void get_dis (int x, int fa) {
	dis[++cnt] = d[x];
	for (auto i : G[x]) {
		int y = i.y, v = i.v;
		if (y == fa || vis[y]) continue;
		d[y] = d[x] + v;
		get_dis (y, x);
	}
}
void calc (int x) {
	int p = 0;
	for (auto i : G[x]) {
		int y = i.y, v = i.v;
		if (vis[y]) continue;
		cnt = 0; d[y] = v;
		get_dis (y, x);
		for (int j = cnt; j; j--)
			for (int q = 1; q <= m; q++)
				if (k[q] >= dis[j])
					ans[q] |= vis2[k[q] - dis[j]];
		for (int j = cnt; j; j--)
			Q[++p] = dis[j], vis2[dis[j]] = 1;
	}
	for (int i = 1; i <= p; i++) vis2[Q[i]] = 0;
}
void solve (int x) {
	vis[x] = vis2[0] = 1;
	calc (x);
	for (auto i : G[x]) {
		int y = i.y, v = i.v;
		if (vis[y]) continue;
		now = siz[y], root = 0;
		f[0] = 1e9 + 7;
		get_root (y, 0);
		solve (root);
	}
}
int main ()
{
	ios::sync_with_stdio (false);
	cin.tie (0); cout.tie (0);
	
	cin >> n >> m; 
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].emplace_back (Edge {v, w});
		G[v].emplace_back (Edge {u, w});
	}
	for (int i = 1; i <= m; i++) cin >> k[i];
	now = n;
	f[0] = N;
	get_root (1, 0);
	solve (root);
	for (int i = 1; i <= m; i++) cout << (ans[i] ? "AYE\n" : "NAY\n");
	return 0;
}
2024/5/21 21:25
加载中...