P14346 题解

设

ans_x

为指定

x

座城市为度假城市的最小费用。

x=1

的情况是平凡的，不妨假设

x\ge 2

。

此时，我们找出包含所有选择的节点的最小连通块，把它缩成一个点，那么从它出发的外向生成树上所有边权之和就是答案。

先将条件加强为“包含所有选择的节点和根节点的最小连通块”。这样我们可以进行树形 dp：令

f_{u,i}

表示

u

子树内选择

i

个节点的最小代价（只考虑

u

子树内的边）。

因为需要包含根节点，所以

i>0

时

u

节点一定在连通块内；否则，

u

子树中所有节点都不在连通块内，此时从

fa_u

连向

u

的边就会在向上转移的时候产生代价。

可以证明

f_u

是下凸的。从

f_v

向

f_u(u=fa_v)

转移时，

f_{v,0}

会产生额外代价，这不影响凸性；而进行

(\min,+)

卷积也不影响凸性。

现在复杂度瓶颈是

O(n^2)

的卷积，但在函数有凸性的情况下可以维护差分数组进行归并——这里由于只有对

f_{v,0}

的修改，用可并堆维护，时间复杂度

O(n\log n)

。

当然唯一的问题是我们选择的连通块不一定包含根节点——这可以用点分治解决。同时处理根节点时需要特判：前面两步必须选择两个不同子树中的节点，贪心即可。如果无法选出，那么当前子树至多有两个节点，这是简单的。

时间复杂度

O(n\log^2 n+Q)

。

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=200007;
ll n,m,ans[N],p[N],f[N],root[N],val[N],lson[N],rson[N],sz[N],mx[N],vis[N];
vector<pair<ll,ll> > to[N];
map<pair<ll,ll>,ll> mp;
int merge(int u,int v){
	if (!u||!v){
		return u|v;
	}
	if (val[u]<val[v]){
		swap(u,v);
	}
	rson[u]=merge(rson[u],v);
	swap(lson[u],rson[u]);
	return u;
}
void reset(int u){
	val[u]=lson[u]=rson[u]=0;
}
int pop(int u){
	return merge(lson[u],rson[u]);
}
void getroot(int u,int fa,int n,int& r){
	sz[u]=1;mx[u]=0;
	for (auto p:to[u]){
		if (vis[p.first]||p.first==fa){
			continue;
		}
		int v=p.first;
		getroot(v,u,n,r);
		mx[u]=max(mx[u],sz[v]);
		sz[u]+=sz[v];
	}
	if (max(mx[u],n-sz[u])*2<=n){
		r=u;
	}
}
void dfs(int u,int fa){
	f[u]=0;root[u]=0;sz[u]=1;
	for (auto p:to[u]){
		if (vis[p.first]||p.first==fa){
			continue;
		}
		int v=p.first;
		dfs(v,u);
		sz[u]+=sz[v];
		f[u]+=f[v]+p.second;
		val[root[v]]+=p.second;
		if (fa){
			root[u]=merge(root[u],root[v]);
		}
	}
	if (root[u]==0&&fa){
		reset(u);
		root[u]=u;
	}
}
void solve(int u,int n,ll dif){
	if (n==1){
		ans[1]=min(ans[1],dif);
		vis[u]=1;
		return;
	}
	if (n==2){
		ans[2]=min(ans[2],dif);
		int v=0;
		for (auto p:to[u]){
			if (!vis[p.first]){
				v=p.first;
				ans[1]=min(ans[1],dif+p.second);
				ans[1]=min(ans[1],dif+mp[make_pair(v,u)]);
				vis[u]=vis[v]=1;
				return;
			}
		}
		return;
	}
	getroot(u,0,n,u);
	dfs(u,0);
	ans[1]=min(ans[1],f[u]+dif);
	int p1=0,p2=0;
	for (auto p:to[u]){
		if (vis[p.first]){
			continue;
		}
		int v=p.first;
		if (val[root[v]]>val[root[p2]]){
			p2=v;
		}
		if (val[root[p2]]>val[root[p1]]){
			swap(p1,p2);
		}
	}
	assert(p1&&p2);
	ll s=f[u]+dif-val[root[p1]]-val[root[p2]];
	ans[2]=min(ans[2],s);
	root[p1]=pop(root[p1]);root[p2]=pop(root[p2]);
	for (auto p:to[u]){
		if (vis[p.first]){
			continue;
		}
		root[u]=merge(root[u],root[p.first]);
	}
	for (int i=3;root[u];++i){
		s-=val[root[u]];
		root[u]=pop(root[u]);
		ans[i]=min(ans[i],s);
	}
	vis[u]=1;
	for (auto p:to[u]){
		if (vis[p.first]){
			continue;
		}
		int v=p.first;
		solve(v,sz[v],dif+f[u]-f[v]-p.second+mp[make_pair(v,u)]);
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	memset(ans,0x3f,sizeof(ans));
	for (int u,v,x,y,i=1;i<n;++i){
		cin>>u>>v>>x>>y;
		to[u].emplace_back(v,x);to[v].emplace_back(u,y);
		mp[make_pair(u,v)]=x;
		mp[make_pair(v,u)]=y;
	}
	solve(1,n,0);
	for (int i=2;i<=n;++i){
		ans[i]=min(ans[i],ans[i-1]);
	}
	cin>>m;
	for (int x,i=1;i<=m;++i){
		cin>>x;
		cout<<ans[x]<<'\n';
	}
	return 0;
}

文章操作

相关推荐

评论

P14346 题解