Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
27040 | gaochunzhen | 【BJ】T3 | C++ | 通过 | 100 | 38 MS | 4584 KB | 2294 | 2024-02-29 19:46:45 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e3 + 9, M = 59; vector<int> G[N]; int n, m, siz[N]; LL L, R, a[N]; vector<__int128_t> dp[N][M], g[M]; void dfs(int u, int fa) { dp[u][0].push_back(a[u]), siz[u] = 1; for (int v : G[u]) { if (v == fa) continue; dfs(v, u); for (int i = 0; i <= m && i < siz[u]; i++) { for (auto j : dp[u][i]) { for (int x = 0; x <= m - i && x < siz[v]; x++) { for (auto y : dp[v][x]) { g[i + x].push_back((__int128_t)(j) + y); if (i + x < m && L <= y && y <= R) g[i + x + 1].push_back(j); } } } } siz[u] += siz[v]; for (int i = 0; i <= m && i < siz[u]; i++) { dp[u][i].clear(); sort(g[i].begin(), g[i].end()); if (!g[i].size()) continue; int l = 0, r = 0; while (r < g[i].size() - 1) { while (r < g[i].size() && g[i][r] - g[i][l] <= R - L + 1) r++; dp[u][i].push_back(g[i][l]), l = --r; } dp[u][i].push_back(g[i][g[i].size() - 1]); g[i].clear(); } } } struct DSU { int fa[N], tot; void init() { for (int i = 1; i <= n; i++) fa[i] = i; tot = n; } int get(int x) { while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x; } void merge(int x, int y) { x = get(x), y = get(y); if (x != y) fa[y] = x, tot--; } } T; signed main() { scanf("%d%d%lld%lld", &n, &m, &L, &R); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } T.init(); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); assert(u >= 1 && u <= n); assert(v >= 1 && v <= n); T.merge(u, v); } assert(T.tot == 1); dfs(1, 0); for (int i = 0; i <= m; i++) { int fl = 0; for (__int128_t j : dp[1][i]) { if (j >= L && j <= R) { fl = 1; break; } } putchar(fl + '0'); } return 0; }