自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:04:19，当前版本为作者最后更新于2024-08-19 11:06:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Problem Link

题目大意

给定 $n$ 个点的树，每个点点权 $a_i$ 有一个限定范围 $[l_i,r_i]$，$q$ 组询问给定 $v$，要求构造一组 $a_i$ 使得树上最大权独立集为 $v$。

数据范围：$n,q\le 2\times 10^5$。

思路分析

考虑所有 $a_i=l_i$ 和所有 $a_i=r_i$ 时的最大权独立集 $v_L,v_R$，容易发现 $v<v_L$ 或 $v>v_R$ 一定无解。

然后考虑每次令某个 $a_u\gets a_u+1$，容易发现此时最大权独立集大小增量 $\in\{0,1\}$。

那么 $v\in[v_L,v_R]$ 时一定有解，我们可以对每个 $a_i$ 依次从 $l_i$ 增加到 $r_i$。

容易发现一定存在某个时刻 $x$ 使得 $a_i\ge x$ 后每次增加 $a_i$，最大独立集的大小也增加，即增加 $a_i$ 会导致最大独立集增加的时刻是一段后缀。

那么我们求出 $a_{1\sim i}$ 变成 $r_x$，$a_{i+1\sim n}$ 为 $l_x$ 时的最大权独立集 $v_i$，找到第一个 $v_i>v$，那么 $a_{1\sim i-1}$ 为 $r_x$，$a_{i+1\sim n}$ 为 $l_x$，$a_i=r_i-(v_i-v)$ 即为一组解。

如果按 $1\sim n$ 的顺序逐个修改，需要用全局平衡二叉树维护 ddp，但是如果按 dfn 序修改，可以简单换根 dp 求出。

时间复杂度 $\mathcal O(n+q\log n)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int n,q,dcnt;
vector <int> G[MAXN];
ll X,Y,M;
ll l[MAXN],r[MAXN],s[MAXN],hv[MAXN],rk[MAXN],p[MAXN],t[MAXN];
array<ll,2> f[MAXN],g[MAXN];
ll hsh(int i,ll z) { return (i*X+z*z%M*Y)%M; }
void dfs1(int u,int fz) {
	f[u]={0,l[u]},g[u]={0,r[u]};
	for(int v:G[u]) if(v^fz) {
		dfs1(v,u);
		f[u][0]+=max(f[v][0],f[v][1]);
		g[u][0]+=max(g[v][0],g[v][1]);
		f[u][1]+=f[v][0];
		g[u][1]+=g[v][0];
	}
}
void dfs2(int u,int fz,array<ll,2>o) {
	rk[++dcnt]=u,hv[dcnt]=hv[dcnt-1]^hsh(u,l[u])^hsh(u,r[u]);
	o[0]+=f[u][0],o[1]+=f[u][1]+r[u]-l[u],s[dcnt]=max(o[0],o[1]);
	for(int v:G[u]) if(v^fz) {
		o[0]-=max(f[v][0],f[v][1]),o[1]-=f[v][0];
		dfs2(v,u,{max(o[0],o[1]),o[0]});
		o[0]+=max(g[v][0],g[v][1]),o[1]+=g[v][0];
	}
}
void solve() {
	scanf("%d%d%lld%lld%lld",&n,&q,&X,&Y,&M);
	for(int i=1;i<=n;++i) G[i].clear();
	for(int i=1,u,v;i<n;++i) {
		scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
	}
	for(int i=1;i<=n;++i) scanf("%lld%lld",&l[i],&r[i]);
	dfs1(1,0);
	s[0]=max(f[1][0],f[1][1]),hv[0]=0;
	for(int i=1;i<=n;++i) hv[0]^=hsh(i,l[i]);
	dcnt=0,dfs2(1,0,{0,0});
	for(int i=1;i<=q;++i) scanf("%lld",&p[i]);
	for(int i=1;i<=q;++i) {
		if(p[i]<s[0]||p[i]>s[n]) printf("-1 ");
		else {
			int j=lower_bound(s,s+n+1,p[i])-s,u=rk[j];
			ll k=s[j]-p[i],ans=hv[j]^hsh(u,r[u])^hsh(u,r[u]-k);
			printf("%lld ",ans);
		}
	}
	puts(""),fflush(stdout);
	while(true) {
		int o; scanf("%d",&o);
		if(!o) break;
		if(p[o]<s[0]||p[o]>s[n]) puts("-1");
		else {
			int j=lower_bound(s,s+n+1,p[o])-s,u=rk[j];
			for(int i=1;i<=j;++i) t[rk[i]]=r[rk[i]];
			for(int i=j+1;i<=n;++i) t[rk[i]]=l[rk[i]];
			t[u]-=s[j]-p[o];
			for(int i=1;i<=n;++i) printf("%lld ",t[i]);
			puts("");
		}
		fflush(stdout);
	}
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}