CF1120D Power Tree——一题多解

本文主要是介绍CF1120D Power Tree——一题多解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

UNFINISHED

https://www.luogu.com.cn/problem/CF1120D

给你一棵树，想象你可以对于每个点 \(x\)，用 \(c_x\) 的花费得到子树中所有叶子的权值和，你想要解出所有叶子的权值，最少要多少花费？（相较于原题，题意有改动，是根据模拟赛的题意来的）\(n\le 10^6,1\le c_x\le 10^9\)

法1.区间转差分的思想+最小生成树

你可以把叶子按从左到右（直观的）看成一个序列，每个点可以对序列的一个可知的区间进行区间查和这样的（想象），运用区间转差分的思想，\([l,r]\) 可以换成 \(\lang l,r+1\rang\)，在一个大小为 \(cnt\_leaf+1\) 的图里将 \(l,r+1\) 连一条权值为 \(c_x\) 的边；只需要最后叶子们都连通，根据 \(n\) 元一次方程组需要 \(n\) 个方程解出，则转化为最小生成树问题。
难点在于第二问，对于最小生成树的边数组（已排序）连续的一段一样的边权的边，合法的都可能，而处理完这一段得到的图的连通性都是一样的，所以不会影响后续。具体不太好说，看代码吧。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,dfc,id_lf,c[N],u[N],v[N],fa[N],lf[N],rf[N],dfn[N],num[N];
vector<int>G[N];
struct J{int u,v,w,id;}e[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void unite(int x,int y){fa[find(y)]=find(x);}
void dfs1(int x,int p){
	bool is_lf=1;
	for(int i=0;i<G[x].size();i++){
		int y=G[x][i];
		if(y^p)is_lf=0,dfs1(y,x);
	}
	if(is_lf)num[x]=++id_lf;
}
void dfsa(int x,int p){
	dfn[++dfc]=x;
	for(int i=0;i<G[x].size();i++){
		int y=G[x][i];
		if(y^p)dfsa(y,x);
	}
	rf[x]=num[dfn[dfc]];
}
void dfsb(int x,int p){
	dfn[++dfc]=x;
	for(int i=0;i<G[x].size();i++){
		int y=G[x][i];
		if(y^p)dfsb(y,x);
	}
	lf[x]=num[dfn[dfc]];
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	for(int i=1;i<n;i++)scanf("%d%d",&u[i],&v[i]);
	for(int i=1;i<n;i++)G[u[i]].push_back(v[i]),G[v[i]].push_back(u[i]);
	dfs1(1,0);for(int i=1;i<=id_lf+1;i++)fa[i]=i;
	dfsa(1,0);
	for(int i=1;i<=n;i++)G[i].clear();
	for(int i=n-1;i;i--)G[u[i]].push_back(v[i]),G[v[i]].push_back(u[i]);
	dfc=0,dfsb(1,0);
	for(int i=1;i<=n;i++)/*cout<<lf[i]<<' '<<rf[i]<<'\n',*/e[i].u=lf[i],e[i].v=rf[i]+1,e[i].w=c[i],e[i].id=i;
	sort(e+1,e+n+1,[](J a,J b){return a.w<b.w;});
	vector<int>st;
	long long sum=0;
	for(int i=1;i<=n;i++){
		int j=i-1;
		while(j<n&&e[j+1].w==e[i].w){
			j++;
			if(find(e[j].u)!=find(e[j].v))st.push_back(e[j].id);
		}
		j=i-1;
		while(j<n&&e[j+1].w==e[i].w){
			j++;
			if(find(e[j].u)!=find(e[j].v))unite(e[j].u,e[j].v),sum+=e[j].w;
		}
		i=j;
	}
	cout<<sum<<' '<<st.size()<<'\n';
	sort(st.begin(),st.end());
	for(int i=0;i<st.size();i++)cout<<st[i]<<' ';
}

法2.DP

也可以用树形dp做，但我还没有调出来，因为我的写法很折腾人。这个做法远远不如法1来得优美，但没办法，你看下面这个plus问题

第三问：最优方案有几种？两种方案不同当且仅当取的 \(x\) 的集合不同。

这篇关于CF1120D Power Tree——一题多解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！