题解：P11111 [ROI 2023] 生产计划 (Day 2)
george0929
·
·
题解
题意
给定一棵树，每个点有两个数 l_i,r_i，多次询问 v，构造点权序列 a 满足 a_i\in [l_i,r_i] 且树上最大独立集恰好为 v（以哈希形式输出），或报告无解。
有保证 $\sum (r_i-l_i)$ 的部分分。
### 题解
判无解是简单的，全取 $l_i$ 求出最大独立集 $L$，全取 $r_i$ 求出最大独立集 $R$，有解当且仅当 $v\in [L,R]$。
考虑部分分怎么做，每次将一个值调大一，独立集要么增加一要么不变。
那么将一个值在 $[l,r]$ 中二分答案可以得出一个值被计入最大独立集的最小值。
考虑询问离线，每次将一个点从 $l_i$ 调为 $r_i$，我们知道一个点被计入独立集后每次 $+1$ 时，独立集也会增加 $1$，因此只需要在初始时进行一次 DP 即可，总共进行 $n\log n$ 次 DP，带 $\log$ 是因为我们二分了一个点被计入独立集的最小权值。
直接 DDP 可以通过，但存在不使用 DDP 的做法。
考虑先去掉 DP 次数的 $\log$，直接将 $a_i$ 改为 $l_i,r_i$ 跑 DP 分别得到独立集 $x,y$，则 $a_i=r_i-y+x$ 时开始计入独立集，原因是 $a_i$ 计入独立集后，$a_i$ 和独立集同增。
之后我们只需要每次选择一个 $a$，将 $a_i$ 从 $l_i$ 改为 $r_i$ 后求出当前独立集即可。
修改顺序可以自己选定，考虑换根 DP，每次改根节点即可（换言之，按 DFS 序进行修改），复杂度 $O(n\log n)$，瓶颈在于对询问排序。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int x,y,m;
struct HashSet{
int res=0;
void init(){
res=0;
}
void upd(int j,int aj){
res=res^((1ll*x*j%m+1ll*y*aj%m*aj%m)%m);
}
}H;
int n,q,l[200005],r[200005],a[200005];
vector<int> V[200005];
ll f[200005][2];
int st;
ll qv[200005];
pair<ll,int> qr[200005];
ll Lv,Rv;
void delsubt(int u,int v){
f[u][0]-=max(f[v][0],f[v][1]);
f[u][1]-=f[v][0];
}
void addsubt(int u,int v){
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
}
void dfs1(int u,int fa){
f[u][0]=0,f[u][1]=a[u];
for(int v:V[u]){
if(v==fa) continue;
dfs1(v,u);
addsubt(u,v);
}
}
int ansk[200005];
int isok;
void dfs2(int u,int fa,ll fl){
if(fl!=-1&&isok) return;
// a_u : l_u -> r_u
H.upd(u,a[u]);//ers
ll Lt=max(f[u][1],f[u][0]),Rt=max(f[u][1]+r[u]-l[u],f[u][0]);
if(fl!=-1&&Lt<=fl&&fl<=Rt){
a[u]=r[u]-(Rt-fl);
isok=1;
return;
}
while(fl==-1&&st<=q&&Lt<=qr[st].first&&qr[st].first<=Rt){
H.upd(u,r[u]-(Rt-qr[st].first));//add
ansk[qr[st].second]=H.res;st++;
H.upd(u,r[u]-(Rt-qr[st-1].first));//ers
}
a[u]=r[u];//add
H.upd(u,a[u]);
f[u][1]+=r[u]-l[u];
for(int v:V[u]){
if(v==fa) continue;
ll tmp0=f[u][0],tmp1=f[u][1];
delsubt(u,v);
addsubt(v,u);
dfs2(v,u,fl);
delsubt(v,u);
addsubt(u,v);
}
}
void solve(){
cin>>n>>q;
cin>>x>>y>>m;
for(int i=1;i<=n;i++) V[i].clear();
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
V[u].push_back(v);
V[v].push_back(u);
}
for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
for(int i=1;i<=q;i++){
cin>>qv[i];
qr[i]={qv[i],i};
}
sort(qr+1,qr+1+q);
for(int i=1;i<=n;i++) a[i]=r[i];
dfs1(1,0);Rv=max(f[1][0],f[1][1]);
for(int i=1;i<=n;i++) a[i]=l[i];
dfs1(1,0);Lv=max(f[1][0],f[1][1]);
st=0;
for(int i=1;i<=q;i++){
if(qr[i].first<Lv||qr[i].first>Rv){
ansk[qr[i].second]=-1;
if(qr[i].first<Lv) st=i;
}
}
st++;
H.init();
for(int i=1;i<=n;i++) H.upd(i,a[i]);
dfs2(1,0,-1);
for(int i=1;i<=q;i++) cout<<ansk[i]<<" ";
cout<<endl;
while(1){
int id;
cin>>id;
if(id==0) break;
if(ansk[id]==-1){
cout<<"-1"<<endl;
continue;
}
isok=0;
for(int i=1;i<=n;i++) a[i]=l[i];
dfs1(1,0);
dfs2(1,0,qv[id]);
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
cout<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
```