题解：P12423 【MX-X12-T6】「ALFR Round 5」Coloring Nodes

首先，无解的情况比较显然，即询问的点为叶子且在

[l,r]

中，然而

[l,r]

并未包含所有叶子。

考虑根固定时怎么做：对于每个点

u

，记录

f,l,r

，分别表示

u

子树内叶子对应的区间是

[l_u,r_u]

，

u

到其子树内所有叶子路径上都有黑点的最小花费为

f_u

，有转移：

f_u\gets\min\{w_u+h_u,g_u\}

其中

g_u=\sum\limits_{v\in\operatorname{son}_u} f_v

，

h_u=\sum\limits_{v\in\operatorname{subtree}_u\setminus\{u\}}[w_v\le 0]w_v

。前者表示的是

u

染黑了的话，那么

u

子树内的叶子到根的路径上都有黑点了，所以它的子树内可以随便染黑；贪心地，染黑全部点权为非负数的点即可。后者表示

u

不染黑，让

u

的每个儿子自己染黑自己子树内的叶子即可。

对于

[l,r]

，显然只有包含和无交两种情况。

现在来考虑怎么求答案。显然，一个点

u

如果对答案的贡献应为

f_u

，并且如果

u

要产生贡献的话，那么它子树内的其它点一定不产生贡献，因此它要对答案贡献的充要条件应该是：

L\le l_u\le r_u\le R\land(l_{fa_u}<L\lor r_{fa_u}>R)

。

注意到如果

u

有贡献，那么它子树内的其它点都会对答案有贡献，考虑把一个点的贡献写成

f_u-g_u

的形式，容易发现，这样的话，对子树求和后的结果就正好为

f_u

。

然后问题就转化为对于所有

L\le l_u\le r_u\le R

的

u

的

f_u-g_u

求和，二维数点即可，可以做到

O(nk\log n+q\log n)

，其中

k

为查询的根数。

接下来考虑换根，容易发现在一次换根时，只有路径两端的点的

f,l,r,g,h

会发生变化，因此考虑在根固定的基础上，加上一维表示每个点作为根的时间戳

t_u

，每次

f,l,r,g,h

变化时撤销旧的贡献并加入新的贡献，每次查询的要求就变成了

t\le t_{u_i},l_i\le l,r\le r_i

，这是一个三维偏序。

实现的时候注意一下叶子需要特判，以及一些可能会导致 TLE 的常数因子，时间复杂度

O((n+q)\log^2(n+q))

。

code

CPP

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,q,m,rt,nowt,tim[N],tot,ans[N],t[N],u[N],l[N][2],r[N][2],_l[N],_r[N],posl[N],posr[N],f[N],g[N],_g[N],h[N],_h[N],w[N],fa[N],cnt[N],c[N];
bool leaf[N];
vector<int> G[N];
struct node{ int t,l,r,w,id; }p[N<<3],pp[N<<3];
bool cmp1(node a,node b){
	if(a.t==b.t){
		if(a.l==b.l){
			if(a.r==b.r) return a.id<b.id;
			return a.r<b.r;
		}
		return a.l>b.l;
	}
	return a.t<b.t;
}
bool cmp2(node a,node b){ return a.l>b.l; }
void dfs1(int u){
	if(leaf[u]){
		f[u]=w[u],g[u]=0;
		l[u][0]=r[u][0]=u,posl[u]=posr[u]=u;
	} else{
		for(auto v:G[u]){
			if(v==fa[u]) continue;
			fa[v]=u;
			dfs1(v);
			g[u]+=f[v];
			h[u]+=h[v];
			if(w[v]<=0) h[u]+=w[v];
			if(l[v][0]<l[u][0]) l[u][1]=l[u][0],l[u][0]=l[v][0],posl[u]=v;
			else l[u][1]=min(l[u][1],l[v][0]);
			if(r[v][0]>r[u][0]) r[u][1]=r[u][0],r[u][0]=r[v][0],posr[u]=v;
			else r[u][1]=max(r[u][1],r[v][0]);
		}
		f[u]=min(g[u],h[u]+w[u]);
	}
	if(f[u]-g[u]) p[++m]=node({tot,l[u][0],r[u][0],f[u]-g[u],0});
}
void dfs2(int u){
	if(f[u]-g[u]) p[++m]=node({tot,l[u][0],r[u][0],-(f[u]-g[u]),0});
	if(!leaf[u]){
		if(min(w[u]+h[u]+_h[u],g[u]+_g[u])-(g[u]+_g[u])){
			p[++m]=node({tot,min(l[u][0],_l[u]),max(r[u][0],_r[u]),min(w[u]+h[u]+_h[u],g[u]+_g[u])-(g[u]+_g[u]),0});
			p[++m]=node({tot+1,min(l[u][0],_l[u]),max(r[u][0],_r[u]),-(min(w[u]+h[u]+_h[u],g[u]+_g[u])-(g[u]+_g[u])),0});
		}
	} else{
		p[++m]=node({tot,min(l[u][0],_l[u]),max(r[u][0],_r[u]),w[u]+_h[u]-_g[u],0});
		p[++m]=node({tot+1,min(l[u][0],_l[u]),max(r[u][0],_r[u]),-(w[u]+_h[u]-_g[u]),0});
	}
	for(auto v:G[u]){
		if(v==fa[u]) continue;
		t[v]=++tot;
		_g[v]=min(w[u]+h[u]+_h[u]-h[v]-(w[v]<=0?w[v]:0),g[u]+_g[u]-f[v]);
		_h[v]=_h[u]+h[u]-h[v]-(w[v]<=0?w[v]:0)+(w[u]<=0?w[u]:0);
		if(posl[u]==v) _l[v]=min(l[u][1],_l[u]);
		else _l[v]=min(l[u][0],_l[u]);
		if(posr[u]==v) _r[v]=max(r[u][1],_r[u]);
		else _r[v]=max(r[u][0],_r[u]);
		if(g[v]-(g[u]+_g[u]-f[v])){
			if(posl[u]==v&&posr[u]==v) p[++m]=node({tot,min(l[u][1],_l[u]),max(r[u][1],_r[u]),_g[v]-(g[u]+_g[u]-f[v]),0});
			else if(posl[u]==v) p[++m]=node({tot,min(l[u][1],_l[u]),max(r[u][0],_r[u]),_g[v]-(g[u]+_g[u]-f[v]),0});
			else if(posr[u]==v) p[++m]=node({tot,min(l[u][0],_l[u]),max(r[u][1],_r[u]),_g[v]-(g[u]+_g[u]-f[v]),0});
			else p[++m]=node({tot,min(l[u][0],_l[u]),max(r[u][0],_r[u]),_g[v]-(g[u]+_g[u]-f[v]),0});
		}
		dfs2(v);
		if(g[v]-(g[u]+_g[u]-f[v])){
			if(posl[u]==v&&posr[u]==v) p[++m]=node({tot+1,min(l[u][1],_l[u]),max(r[u][1],_r[u]),-(_g[v]-(g[u]+_g[u]-f[v])),0});
			else if(posl[u]==v) p[++m]=node({tot+1,min(l[u][1],_l[u]),max(r[u][0],_r[u]),-(_g[v]-(g[u]+_g[u]-f[v])),0});
			else if(posr[u]==v) p[++m]=node({tot+1,min(l[u][0],_l[u]),max(r[u][1],_r[u]),-(_g[v]-(g[u]+_g[u]-f[v])),0});
			else p[++m]=node({tot+1,min(l[u][0],_l[u]),max(r[u][0],_r[u]),-(_g[v]-(g[u]+_g[u]-f[v])),0});
		}
	}
	if(f[u]-g[u]) p[++m]=node({tot+1,l[u][0],r[u][0],f[u]-g[u],0});
}
int lowbit(int x){ return x&-x; }
void add(int x,int y){
	for(;x<=n;x+=lowbit(x)){
		if(tim[x]!=nowt) c[x]=0,tim[x]=nowt;
		c[x]+=y;
	}
}
int ask(int x){
	int s=0;
	for(;x;x-=lowbit(x)) if(tim[x]==nowt) s+=c[x];
	return s;
}
void cdq(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;
	cdq(l,mid),cdq(mid+1,r);
	++nowt;
	int pos=l-1;
	for(int i=mid+1;i<=r;++i){
		while(pos+1<=mid&&p[pos+1].l>=p[i].l){
			++pos;
			if(!p[pos].id) add(p[pos].r,p[pos].w);
		}
		if(p[i].id) ans[p[i].id]+=ask(p[i].r);
	}
	int tot=0,pl=l,pr=mid+1;
	while(pl<=mid||pr<=r)
		if(pr>r||(pl<=mid&&p[pl].l>=p[pr].l)) pp[++tot]=p[pl++];
		else pp[++tot]=p[pr++];
	for(int i=1;i<=tot;++i) p[l+i-1]=pp[i];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;++i) cin>>w[i];
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	if(n==1){
		while(q--) cout<<w[1]<<endl;
		return 0;
	}
	for(int i=1;i<=n;++i)
		if(G[i].size()==1) leaf[i]=true;
		else rt=i;
	for(int i=1;i<=n;++i) cnt[i]=cnt[i-1]+leaf[i];
	t[rt]=tot=1;
	memset(l,0x3f,sizeof(l)),memset(r,-0x3f,sizeof(r));
	dfs1(rt);
	memset(_l,0x3f,sizeof(_l)),memset(_r,-0x3f,sizeof(_r));
	dfs2(rt);
	for(int i=1,u,l,r;i<=q;++i){
		cin>>u>>l>>r;
		if(leaf[u]&&l<=u&&u<=r&&cnt[r]-cnt[l-1]!=cnt[n]){
			ans[i]=1e18;
			continue;
		}
		p[++m]=node({t[u],l,r,1,i});
	}
	stable_sort(p+1,p+m+1,cmp1);
	cdq(1,m);
	for(int i=1;i<=q;++i)
		if(ans[i]==1e18) cout<<"Impossible"<<endl;
		else cout<<ans[i]<<endl;
	return 0;
}

题解：P12423 【MX-X12-T6】「ALFR Round 5」Coloring Nodes

文章操作

相关推荐

评论

题解：P12423 【MX-X12-T6】「ALFR Round 5」Coloring Nodes