[BZOJ 5072]小A的树

Description

题库链接

给你 \(n\) 个节点的一棵树,点分黑白。 \(q\) 组询问,每次询问类似于“是否存在树中 \(x\) 个点的连通块恰有 \(y\) 个黑点”。 \(t\) 组数据。

\(1\leq t\leq 5,1\leq n\leq 5000,q\leq 10^5\)

Solution

由于询问比较多,容易猜到一个结论,就是 \(x\) 个点的连通块能取到黑点的个数一定是完整的一段区间。

就是只要 \(y\geq\) \(x\) 个点的连通块黑点个数的下界,且 \(y\leq\) \(x\) 个点的连通块黑点个数的上界,那么就满足题设条件。

具体证明,大概就是在 \(x\) 个点的连通块中删去边界一个点,再加上另一个不在连通块内的点这样黑点增量(减量)是不大于 \(1\) 的,那么就一定能取到一整段区间内的数。

可以用 \(O(n^2)\) 的树上背包来预处理出这个上界下界。最后 \(O(1)\) 回答询问即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 5000+5; int n, q, d[N], u, v, f[N][N], g[N][N], size[N];
struct tt {int to, next; }edge[N<<1];
int path[N], top; void dfs(int u, int fa) {
if (d[u] == 1) f[u][1] = g[u][1] = 1;
else f[u][1] = g[u][1] = 0;
size[u] = 1;
for (int i = path[u], v; ~i; i = edge[i].next)
if ((v = edge[i].to) != fa) {
dfs(v, u);
for (int p = size[u]; p; p--)
for (int q = size[v]; q; q--)
f[u][p+q] = min(f[u][p+q], f[u][p]+f[v][q]),
g[u][p+q] = max(g[u][p+q], g[u][p]+g[v][q]);
size[u] += size[v];
}
for (int i = 1; i <= size[u]; i++)
f[0][i] = min(f[0][i], f[u][i]), g[0][i] = max(g[0][i], g[u][i]);
}
void add(int u, int v) {edge[++top] = (tt){v, path[u]}; path[u] = top; }
void work() {
memset(path, top = -1, sizeof(path));
scanf("%d%d", &n, &q);
for (int i = 1; i < n; i++) scanf("%d%d", &u, &v), add(u, v), add(v, u);
for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
memset(f, 127/3, sizeof(f)), memset(g, 0, sizeof(g));
dfs(1, 0);
while (q--) {
scanf("%d%d", &u, &v);
if (f[0][u] <= v && v <= g[0][u]) puts("YES");
else puts("NO");
}
puts("");
}
int main() {int t; cin >> t; while (t--) work(); return 0; }
上一篇:【BZOJ3926】诸神眷顾的幻想乡 【广义后缀自动机】


下一篇:ABAP CDS 替换对象(Replacement Objects)引起的数据错误