CF1120 D. Power Tree 巧妙的图论转化

这篇具有很好参考价值的文章主要介绍了CF1120 D. Power Tree 巧妙的图论转化。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

传送门

[前题提要]:无

题目描述:

就是给你一棵树,然后每个点有花费,然后你可以选一个点,付费后对这个点的子树的所有叶子结点增减任意权值.
考虑有一个人会给这棵树的所有叶子结点赋值(值我们不知道),输出最小的花费,使得无论它如何赋值,我们使用上述的花
费都能使所有的叶子节点变为0

考虑对一个点的子树的所有叶子节点进行增减任意值.不难联想到对一个点的子树的所有节点增减任意值的做法.所以考虑使用类似于树链剖分的方式将树上修改化为链上区间修改.
考虑记录一个点的所有叶子节点,并且按照 d f s dfs dfs序将其离散化存下.按照 d f s dfs dfs序的性质,我们会发现一个点的所有叶子节点必然是连续的区间.那么此时我们的问题就变成了:
给你 n n n个可以修改的区间,每一个区间都有其修改范围,修改每一个区间需要一定花费,问你至少需要多少花费将所有数字变为0
考虑到区间修改以及单点查询,我们想到使用差分来解决.假设我们使用一个差分数组 k [ i ] = a [ i ] − a [ i − 1 ] k[i]=a[i]-a[i-1] k[i]=a[i]a[i1],那么对于每一次区间修改来说,我们都是 a [ l ] + = v a l , a [ r + 1 ] − = v a l a[l]+=val,a[r+1]-=val a[l]+=val,a[r+1]=val,那么最终我们需要得到的所有的 k [ i ] = = 0 k[i]==0 k[i]==0.
此时有一个巧妙的转化,考虑我们需要所有的k[i]变为0,但是显然我们的差分数组是不改变前缀和的,所以此时所有的值肯定都转移到了cnt+1的位置(假设我们有cnt个叶子节点),那么对于我们的数的转移来说,我们只能将 l l l转移到 r + 1 r+1 r+1,如果我们将转移过程看成边,将每一个叶子结点看成点,那么我们想将所有的值都转移到 c n t + 1 cnt+1 cnt+1,就需要所有的点都联通才行,这样才能保证无论怎么赋值我们都可以将其转移到 c n t + 1 cnt+1 cnt+1的位置
那么此时这道题就简单了,考虑到必须所有点都联通,每次选择联通一个点我们都需要花费,又需要花费最小,所以显然是个最小生成树的模型,此时使用最小生成树跑一下就行.

但是还有一个问题,那就是这道题的最终问题是所有的可能性的最小生成树的点,所以我们用朴素的 k r u s k a l kruskal kruskal跑出来的只是一棵树,需要改一下.考虑到最小生成树的性质,当边相同时,我们可以选择任意一条不在联通块中的边,所以这些边显然都是平等的,所以这些边都是我们的答案(当然这一点是可以严谨证明的,但是限于篇幅,此处不再赘述)


下面是具体的代码部分:文章来源地址https://www.toymoban.com/news/detail-693949.html

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
inline void print(__int128 x){
	if(x<0) {putchar('-');x=-x;}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int w[maxn];vector<int>edge[maxn];int l[maxn],r[maxn];
int cnt=0;
void dfs(int u,int per_u) {
	if(edge[u].size()==1&&u!=1) {
		++cnt;l[u]=r[u]=cnt;
	}
	for(auto v:edge[u]) {
		if(v==per_u) continue;
		dfs(v,u);
		l[u]=min(l[u],l[v]);
		r[u]=max(r[u],r[v]);
	}
}
struct Edge{
	int u,v,w,id;
	bool operator < (const Edge &rhs) const {
		return w<rhs.w;
	}
}edge2[maxn];
int fa[maxn];
int find(int x) {
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}
signed main() {
	int n=read();
	for(int i=1;i<=n;i++) {
		w[i]=read();
	}
	for(int i=1;i<n;i++) {
		int u=read();int v=read();
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	memset(l,0x3f,sizeof l);
	memset(r,-0x3f,sizeof r);
	dfs(1,0);
	for(int i=1;i<=n;i++) {
		int u=l[i],v=r[i];
		edge2[i]={u,v+1,w[i],i};
	}
	for(int i=1;i<=cnt;i++) fa[i]=i;
	sort(edge2+1,edge2+1+n);
	vector<int>ans;int this_cnt=0;int need=0;
	for(int i=1;i<=n;i++) {
		int r=i;
		while(r+1<=n&&edge2[r+1].w==edge2[r].w) r++;
		for(int j=i;j<=r;j++) {
			auto [u,v,w,k]=edge2[j];
			if(find(u)!=find(v)) {
				this_cnt++;ans.push_back(k);
			}
		}
		for(int j=i;j<=r;j++) {
			auto [u,v,w,k]=edge2[j];
			if(find(u)!=find(v)) {
				need+=w;
				fa[find(u)]=find(v);
			}
		}
		i=r;
	}
	sort(ans.begin(),ans.end());
	cout<<need<<" "<<ans.size()<<endl;
	for(auto i:ans) cout<<i<<" ";
	return 0;
}

到了这里,关于CF1120 D. Power Tree 巧妙的图论转化的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • D. Paths on the Tree

    Problem - 1746D - Codeforces 思路:先分析一下题意,根据第一条性质,每次只能够从1开始,而第二条性质则表明对于每个节点来说,经过这个节点的子节点的路径条数应该尽量均衡,最大值与最小值相差不能超过1,所以我们考虑,如果当前要选择k个路径,而当前节点有cnt个子节

    2024年02月09日
    浏览(36)
  • D. Li Hua and Tree(set操作)

    Problem - D - Codeforces   李华有一个有n个顶点和n -1条边的树。树的根是顶点1。每个顶点i的重要性为a。将子树的大小表示为该子树中顶点的数量,将重要性表示为该子树中顶点的重要性之和。将非叶顶点的重子结点表示为具有最大子树大小的子结点。如果存在多个重子,则重子

    2023年04月13日
    浏览(44)
  • 美丽的图论

    **美丽的图论 ** Prüf 😉 对于 n 个顶点上的树的数量 n^(n-2),这是凯莱公式,用于计算 n 个顶点上的树的数量,被放置在一个由 4 个标记顶点组成的圆圈中。 使用 Figma 制作 在图论中,树只是一个没有环的图。 树在离散数学的许多现实世界应用中都很重要。从大脑中的神经元

    2024年02月08日
    浏览(30)
  • 【*1900 图论】CF1328 E

    Problem - E - Codeforces 题意: 思路: 注意到题目的性质:满足条件的路径个数是极少的,因为每个点离路径的距离 =1 先考虑一条链,那么直接就选最深那个点作为端点即可 为什么,因为我们需要遍历所有点的父亲 推广到树,也是要遍历所有点的父亲 为什么要加枚举的tag,因为

    2024年02月15日
    浏览(34)
  • 【学习笔记】CF1783G Weighed Tree Radius

    如果 w v ( u ) w_v(u) w v ​ ( u ) 指代的就是直径,或者说我们再添一项 a v a_v a v ​ ,那么我们几乎就做完了。 于是自然而然想到换一个定义: d ( u , v ) = dist ( u , v ) + a u + a v d(u,v)=text{dist}(u,v)+a_u+a_v d ( u , v ) = dist ( u , v ) + a u ​ + a v ​ 。 发现这样转化过后,设直径的两个端点

    2024年02月16日
    浏览(35)
  • 【简单图论】CF1833 E

    Problem - E - Codeforces 题意:    思路: 显然,最大值就是什么边都不连的连通块个数,最小值就是能连的都连上 那就是,如果一个连通块存在度为1的点,就把它当作接口连接 Code:

    2024年02月16日
    浏览(36)
  • CF963B Destruction of a Tree 题解

      洛谷题目链接   这里提供一个较为朴素的 DP 想法。   给定一棵树,节点个数不超过 (2 times 10^5) ,每次可以删掉度数为偶数的点。问最后能不能删完;能删完给出删除方案。   首先可以随便选一个点作为根。   其次,我们考虑在一棵子树的删除情况,我们令

    2024年02月08日
    浏览(38)
  • 【*1900 图论+枚举思想】CF1328 E

    Problem - E - Codeforces 题意: 思路: 注意到题目的性质:满足条件的路径个数是极少的,因为每个点离路径的距离 =1 先考虑一条链,那么直接就选最深那个点作为端点即可 为什么,因为我们需要遍历所有点的父亲 推广到树,也是要遍历所有点的父亲 为什么要加枚举的tag,因为

    2024年02月14日
    浏览(41)
  • 【简单图论】CF898 div4 H

    Problem - H - Codeforces 题意: 思路: 手玩一下样例就能发现简单结论: v 离它所在的树枝的根的距离 m 离这个根的距离时是 YES 否则就是NO 实现就很简单,先去树上找环,然后找出这个根,分别给a 和 b BFS一遍,得出两个dis数组,比较一下即可 对于只有的环情况 和 m = v 的情况需

    2024年02月07日
    浏览(48)
  • 【图论经典题目讲解】CF715B - Complete The Graph

    D e s c r i p t i o n mathrm{Description} Description 给定一张 n n n 个点, m m m 条边的无向图,点的编号为 0 ∼ n − 1 0sim n-1 0 ∼ n − 1 ,对于每条边权为 0 0 0 的边赋一个不超过 1 0 18 10^{18} 1 0 18 的 正整数 权值,使得 S S S 到 T T T 的最短路长度为 L L L 。 S o l u t i o n mathrm{Solution} Solut

    2024年02月19日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包