题意
给定一棵 \(n\) 个点的树，点 \(i\) 的点权 \(a_i\) 可以被赋为 \([l_i,r_i]\) 中的任意整数。\(q\) 次询问 \(k\)，判断是否存在一种赋点权的方式，使得最大权独立集为 \(k\)。可能需要给出构造。\(2\leq n\leq 2\times 10^5\)，\(1\leq q\leq 2\times 10^5\)。
题解
求出令所有 \(a_i\gets l_i\) 时的最大权独立集 \(L\)，和令所有 \(a_i\gets r_i\) 时的最大权独立集 \(R\)。显然若 \(k<L\) 或 \(k>R\) 则无解。
考虑调整法，考察一个节点 \(i\)，初始时令 \(a_i\gets l_i\)，然后不断令 \(a_i\gets a_i+1\) 直到 \(a_i=r_i\)。可以发现必然是 \(a_i\) 取一段前缀时最大权独立集不变，之后每次操作最大权独立集都会 \(+1\)。考虑按照 \(i=1\sim n\) 的顺序对节点 \(i\) 执行上述操作，则最大权独立集可以取遍 \([L,R]\) 中的所有数，因此 \(L\leq k\leq R\) 时必然有解。
由此可以给出构造。令 \(v_i\) 表示对于 \(1\leq j<i\)，令 \(a_j\gets l_j\)，对于 \(i\leq j\leq n\)，令 \(a_j\gets r_j\) 时的最大权独立集。那么对于一个询问 \(k\)，我们只需找到最小的 \(i\) 使得 \(v_i\geq k\)，将 \(a_i\) 调整到 \(r_i-(v_i-k)\) 即可。
仅剩的问题就是如何快速求出 \(v_i\)。可以视作带修最大权独立集，动态 DP 维护之。需要用全局平衡二叉树做到 \(\mathcal{O}((n+q)\log{n})\) 才能通过。
存在更简单的做法。注意到点的顺序是可以任意钦定的，因此考虑按照 DFS 序修改点权，此时可以换根 DP 维护，DFS 到点 \(u\) 时将 \(v_u\) 从 \(l_u\) 修改成 \(r_u\) 即可。时间复杂度优化到 \(\mathcal{O}(n+q\log{n})\)。
代码
#include <bits/stdc++.h>using namespace std;#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
const int N = 2e5 + 5;template<typename T> inline void chk_min(T &x, T y) { x = min(x, y); }
template<typename T> inline void chk_max(T &x, T y) { x = max(x, y); }int T, n, q, X, Y, M;
int l[N], r[N], a[N];
int stmp, rdfn[N], h[N];
ll f[N][2], val[N], qr[N];struct AdjList {int tot, head[N], nxt[N << 1], to[N << 1];void init() { tot = 0, fill(head + 1, head + n + 1, 0); }void ins(int x, int y) { to[++tot] = y, nxt[tot] = head[x], head[x] = tot; }
} tr;int calc(int u, int val) {return ((ll)X * u % M + (ll)Y * val % M * val % M) % M;
}void dfs1(int x, int fx) {f[x][0] = 0, f[x][1] = l[x];for (int i = tr.head[x]; i; i = tr.nxt[i]) {int y = tr.to[i];if (y == fx) continue;dfs1(y, x);f[x][0] += max(f[y][0], f[y][1]), f[x][1] += f[y][0];}
}
void dfs2(int x, int fx) {rdfn[++stmp] = x;h[stmp] = h[stmp - 1] ^ calc(x, l[x]) ^ calc(x, r[x]);f[x][1] += r[x] - l[x];val[stmp] = max(f[x][0], f[x][1]);for (int i = tr.head[x]; i; i = tr.nxt[i]) {int y = tr.to[i];if (y == fx) continue;f[x][0] -= max(f[y][0], f[y][1]), f[x][1] -= f[y][0];f[y][0] += max(f[x][0], f[x][1]), f[y][1] += f[x][0];dfs2(y, x);f[y][0] -= max(f[x][0], f[x][1]), f[y][1] -= f[x][0];f[x][0] += max(f[y][0], f[y][1]), f[x][1] += f[y][0];}
}int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> T;while (T--) {cin >> n >> q >> X >> Y >> M;tr.init();for (int i = 1, u, v; i < n; ++i)cin >> u >> v, tr.ins(u, v), tr.ins(v, u);for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i];for (int i = 1; i <= q; ++i) cin >> qr[i];dfs1(1, 0);h[0] = 0;for (int i = 1; i <= n; ++i) h[0] ^= calc(i, l[i]);val[0] = max(f[1][0], f[1][1]);stmp = 0, dfs2(1, 0);for (int i = 1; i <= q; ++i) {if (qr[i] < val[0] || qr[i] > val[n]) cout << "-1 ";else {int x = lower_bound(val, val + n + 1, qr[i]) - val, u = rdfn[x];ll d = val[x] - qr[i];cout << (h[x] ^ calc(u, r[u]) ^ calc(u, r[u] - d)) << ' ';}}cout << endl;int id;while (cin >> id && id) {if (qr[id] < val[0] || qr[id] > val[n]) cout << "-1" << endl;else {int x = lower_bound(val, val + n + 1, qr[id]) - val, u = rdfn[x];ll d = val[x] - qr[id];for (int i = 1; i < x; ++i) a[rdfn[i]] = r[rdfn[i]];a[u] = r[u] - d;for (int i = x + 1; i <= n; ++i) a[rdfn[i]] = l[rdfn[i]];for (int i = 1; i <= n; ++i) cout << a[i] << ' ';cout << endl;}}}return 0;
}