MnZn刚学淀粉质,求调,#4, #6, #7, #9 WA了
查看原帖
MnZn刚学淀粉质,求调,#4, #6, #7, #9 WA了
731709
georgeyu123楼主2023/7/25 20:54
# include <bits/stdc++.h>
using namespace std;

# define ll long long

# define N 10005
# define M 1005
# define MAXD 10000005
# define inf 0x3f3f3f3f

vector<pair<int, int> > G[N];

namespace DFZ { 
int n, m, q[M], maxx[N], sz[N];
int rt = 0, sum = 0, dist[N], dd[N], cnt = 0;
bool tf[MAXD], vis[N], ans[M];
inline void dfs_sz(int u, int fa) { 
	sz[u] = 1;
	maxx[u] = 0;
	for (auto [v, w] : G[u]) { 
		if (v != fa && !vis[v]) {
			dfs_sz (v, u);
			sz[u] += sz[v];
			maxx[u] = max (maxx[u], sz[v]);
		}
	}
	maxx[u] = max(maxx[u], sum - sz[u]);
	if (maxx[u] < maxx[rt]) { 
		rt = u;
	}
}

inline void calcdist (int u, int fa) { 
	dd[++cnt] = dist[u];
	for (auto [v, w] : G[u]) { 
		if (v != fa && !vis[v]) {
			dist[v] = dist[u] + w;
			calcdist(v, u);
		}
	}
}

queue<int> tag;
inline void dfz (int u, int fa)  {
	tag.push(0);
	tf[0] = 1;
	vis[u] = 1;
	for (auto [v, w] : G[u]) { 
		if (v != fa && !vis[v]) { 
			dist[v] = w;
			calcdist(v, u);
			for (int k = 1; k <= cnt; ++k) { 
				for (int i = 1; i <= m; ++i) { 
					if (q[i] >= dd[k]) {
						ans[i] |= tf[q[i] - dd[k]];
					}
				}
			}
			for (int k = 1; k <= cnt; ++k) { 
				if (dd[k] <= N - 5) { 
					tag.push(dd[k]);
					tf[dd[k]] = 1;
				}
			}
			cnt = 0;
		}
	}
	while (!tag.empty ()) { 
		tf[tag.front()] = 0, tag.pop();
	}
	for (auto [v, w] : G[u]) { 
		if (v != fa && !vis[v]) {
			rt = 0;
			maxx[rt] = inf;
			sum = sz[v];
			dfs_sz (v, u);
			dfs_sz (rt, -1);
			dfz (rt, u);
		} 
	}
}
} // namespace DFZ
using namespace DFZ;

signed main() {
	cin >> n >> m;
	for (int i = 1, u, v, w; i < n; ++i) { 
		cin >> u >> v >> w;
		G[u].push_back(make_pair(v, w));
		G[v].push_back(make_pair(u, w));
	}
	for (int i = 1; i <= m; ++i) { 
		cin >> q[i];
	}
	rt = 0;
	maxx[rt] = inf;
	sum = n;
	dfs_sz (1, -1);
	dfs_sz (rt, -1);
	dfz (rt, -1);
	for (int i = 1; i <= m; ++i) { 
		if (ans[i]) { 
			cout << "AYE\n";
		} else { 
			cout << "NAY\n";
		}
	}
  return 0;
}
2023/7/25 20:54
加载中...