当前位置 博文首页 > ApocalypseTq的博客:师姐不要(雾
这提示源自_OWO_出的,核心意思看题目去。我这里直接上代码,~~其实这题也就蓝的,硬备搞成紫色~~
#include <bits/stdc++.h>
#define il inline
#define _for(i, a, b) for (int i = (a); i <= (b); ++i)
#define _fore(i, u) for (int i = hd[u], v; v = tg[i], i; i = nx[i])
using namespace std;
struct {
template <typename T>
il operator T() {
T x = 0, f = 1;
char c = getchar();
while (!isdigit(c)) (c == '-') && (f = -1), c = getchar();
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f * x;
}
} gi;
const int M = 1e6 + 5, N = 2e3 + 5, T = 4e3 + 5;
const int inf = 0x3f3f3f3f;
vector<tuple<int, int>> q[N];
vector<int> E[N];
int n, m;
int a[N];
int f[T];
int st[N], ed[N], tim, id[N];
int siz[N], hs[N];
int mxt;
int ans[M];
void pdfs(int u, int fa) {
siz[u] = 1, st[u] = ++tim, id[tim] = u;
for (auto v : E[u])
if (v != fa) {
pdfs(v, u), siz[u] += siz[v];
if (siz[v] > siz[hs[u]]) hs[u] = v;
}
ed[u] = tim;
}
void upd(int v) {
for (int i = mxt; i >= v; --i) f[i] = min(f[i], f[i - v] + 1);
}
void clear() { memset(f, 0x3f, sizeof(f)), f[0] = 0; }
void dfs(int u, int fa, int kep) {
for (auto v : E[u])
if (v != fa && v != hs[u]) dfs(v, u, 0);
if (hs[u]) dfs(hs[u], u, 1);
upd(a[u]);
for (auto v : E[u])
if (v != fa && v != hs[u])
for (int p = st[v]; p <= ed[v]; ++p) upd(a[id[p]]);
for (auto [t, id] : q[u]) ans[id] = (f[t] == inf ? -1 : f[t]);
if (!kep) clear();
}
int main() {
n = gi, m = gi;
for (int i = 1; i <= n; ++i) a[i] = gi;
for (int i = 1, u, v; i < n; ++i) u = gi, v = gi, E[u].push_back(v), E[v].push_back(u);
for (int i = 1, u, t; i <= m; ++i) u = gi, t = gi, q[u].emplace_back(t, i), mxt = max(mxt, t);
pdfs(1, 0);
clear();
dfs(1, 0, 1);
for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
return 0;
}
cs