lottle1212 @ 2023-07-24 21:15:30
像我这种写法的,
#include <iostream>
using namespace std;
typedef long long ll;
const ll N = 1e4 + 10, M = 1e2 + 10, INF = 1e7 + 10;
ll n, m, u, v, w, cnt, tot, Min, sum, rt, head[N], sz[N], dis[N], d[N], q[INF], ask[M];
bool del[N], ans[M], judge[INF];
ll rd() {
ll sum = 0; bool f = 0; char ch = getchar();
while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
while (ch >= '0' && ch <= '9') sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
return f ? -sum : sum;
}
struct Edge { ll nxt, to, w; } e[N << 1];
void add(ll u, ll v, ll w) { e[++ cnt] = {head[u], v, w}; head[u] = cnt; }
void get_rt(ll u, ll pre) {
sz[u] = 1; ll mx = 0;
for (ll i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (v == pre || del[v]) continue;
get_rt(v, u);
sz[u] += sz[v], mx = max(mx, sz[v]);
}
mx = max(mx, sum - sz[u]);
if (mx < Min) Min = mx, rt = u;
}
void get_dis(ll u, ll pre) {
dis[++ tot] = d[u];
for (ll i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (v == pre || del[v]) continue;
d[v] = d[u] + e[i].w;
get_dis(v, u);
}
}
void calc(ll u) {
del[u] = judge[0] = 1; ll top = 0;
for (ll i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (del[v]) continue;
tot = 0, d[v] = e[i].w;
get_dis(v, u);
for (ll j = 1; j <= tot; ++ j)
for (ll k = 1; k <= m; ++ k)
if (ask[k] >= dis[j])
ans[k] |= judge[ask[k] - dis[j]];
for (ll j = 1; j <= tot; ++ j)
if (dis[j] < INF)
q[++ top] = dis[j], judge[dis[j]] = 1;
}
for (ll i = 1; i <= top; ++ i) judge[q[i]] = 0;
}
void divide(ll u) {
calc(u);
for (ll i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (del[v]) continue;
Min = sum = sz[v];
get_rt(v, 0);
divide(rt);
}
}
signed main() {
n = rd(), m = rd();
for (ll i = 1; i < n; ++ i) u = rd(), v = rd(), w = rd(), add(u, v, w), add(v, u, w);
for (ll i = 1; i <= m; ++ i) ask[i] = rd();
Min = sum = n, get_rt(1, 0);
divide(rt);
for (ll i = 1; i <= m; ++ i) puts(ans[i] ? "AYE" : "NAY");
return 0;
}
by zzafanti @ 2023-07-26 07:17:25
lca的这篇博客 说了这个问题,这么做不影响复杂度,您可以看一下qwq