首页 > 其他分享 >洛谷 Power Tree 题解

洛谷 Power Tree 题解

时间:2023-10-03 21:47:53浏览次数:42  
标签:洛谷 Power int 题解 Tree 叶子 EDGE 节点

题目链接

Power Tree

分析

将叶子节点按dfs序重标号后,每次控制操作可以转化为将子树内叶子节点所在区间加(或减)一个数

不难可以想到将叶子区间进行差分
每次对 \(l\) 到 \(r\) 的操作可以转化为将 \(l\) 上的数转移到 \(r+1\) 上
每次操作后差分数组的和不变
将所有点权变为 \(0\) 即为将所有数转移到 最后的叶子节点编号 \(+1\)(记为 \(n+1\)) 上
将所有节点与 \(n+1\) 直接或间接连边即可

将每个原节点转化为从左叶子到右叶子 \(+1\) 的边,边权为 \(w[i]\) ,求最小生成树即可
对于输出答案,将边权相同的边划分成一段,当枚举到段首时,先判断该段中那些边可以加入,并计入答案,再正常进行 &Kruskal& 即可

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=201005;

int n;

struct EDGE{
	int l,r,w,id;
}e[N];
bool cmp(EDGE a,EDGE b){
	return a.w<b.w;
}

int head[N],ne[N*2],v[N*2],tot=0;
void add(int x,int y){
	ne[++tot]=head[x];
	head[x]=tot;
	v[tot]=y;
}

int de[N],dfn[N],cn=0,dsiz[N],siz[N],df[N],cntt=0,;
//dsiz为子树中叶子节点的数量
//df为连续的叶子节点的编号 
void dfs(int u,int fu){
	dfn[u]=++cn;siz[u]=1;
	if(de[u]==1&&u!=1) dsiz[u]=1,df[dfn[u]]=++cntt;
	for(int i=head[u];i;i=ne[i]){
		if(v[i]==fu) continue;
		dfs(v[i],u);
		dsiz[u]+=dsiz[v[i]];
		siz[u]+=siz[v[i]];
	}
}

int fa[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

int ans[N],cnt=0,an=0;
void kr(){
	for(int i=1;i<=cn;i++) fa[i]=i;
	sort(e+1,e+n+1,cmp);
	e[0].w=-1;//有的数据边权为0 
	for(int i=1;i<=n;i++){
		int x=e[i].l,y=e[i].r,id=e[i].id,w=e[i].w;
		if(w!=e[i-1].w){//判断权值相同的边是否可能成为答案 
			for(int l=i;l<=n;l++){
				int p=find(e[l].l),q=find(e[l].r);
				if(p!=q) ans[++cnt]=e[l].id;
				if(e[l+1].w!=e[l].w) break;
			}
		}
		int p=find(x),q=find(y);
		if(p==q) continue;
		fa[p]=q;
		an+=w;
	}
}

signed main(){
	scanf("%lld", &n);
	for(int i=1;i<=n;i++){
		scanf("%lld", &e[i].w);
		e[i].id=i;
	}
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%lld %lld", &x ,&y);
		de[x]++;de[y]++;
		add(x,y);add(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++) e[i].r=df[dfn[i]+siz[i]-1]+1,e[i].l=df[dfn[i]+siz[i]-1]-dsiz[i]+1;//建边 
	kr();
	
	sort(ans+1,ans+cnt+1);
	printf("%lld %lld\n", an, cnt);
	for(int i=1;i<=cnt;i++) printf("%lld ", ans[i]);
	return 0;
}

标签:洛谷,Power,int,题解,Tree,叶子,EDGE,节点
From: https://www.cnblogs.com/Idtwtei/p/17741685.html

相关文章

  • [题解] CF632F - Swimmers in the Pool
    CF632F-SwimmersinthePool题目传送门题意给定一个大小为\(n\timesn\)的矩阵\(A\)。假设\(A\)满足以下条件,那么称该矩阵为MAGIC,否则为NOTMAGIC,并输出对应的属性(即\(A\)是MAGIC还是NOTMAGIC)。$A_{i,j}=A_{j,i}$;$A_{i,i}=0$;$A_{i,j}\le......
  • 洛谷P5303
    这一道题跟NOIP集训模拟赛1的D题非常像,当然D题的递推方程更复杂(磁盘里面有题解pdf)对于这一道题,我们设f[i][0]表示铺了i列而且全部用的完整的砖的方案数f[i][1]表示铺了i列,但是第i列缺了一个而且第i列的唯一的那一块砖头就是1X1其中一个f[i][2]表示铺了i列,但是第i列缺了一个而且......
  • GDCPC2023 B , D , F , K 题解
    和队友一起打的2023年广东省大学生程序设计竞赛重现赛,写了B,D,K,胡了一个F。D题目大意随着广东的建设与发展,越来越多人选择来到广东开始新生活。在一片新建的小区,有\(n\)个人要搬进\(m\)栋排成一行的房子,房子的编号从\(1\)到\(m\)(含两端)。房子\(u\)和\(v\)相邻......
  • 题解 [CSP-S 2021] 括号序列
    题目链接对于括号题,基本是栈匹配没有匹配的左括号和区间\(dp\)两个方向。这道题括号序列并不确定,只能用区间\(dp\)搞。如果直接设\(f_{l,r}\)表示\(l\simr\)的合法括号序列,那么由区间\(dp\)的套路可知,需要枚举中间点进行合并,那么\(()()()\)的情况就会出问题,原因是......
  • 【UVA 12100】Printer Queue 题解(队列+优先队列)
    计算机科学学生会中唯一的打印机正经历着极其繁重的工作量。有时,打印机队列中有100个作业,您可能需要等待数小时才能获得一页输出。由于某些作业比其他作业更重要,黑客将军为打印作业队列发明并实现了一个简单的优先级系统。现在,为每个作业分配1到9之间的优先级(9是最高优先级,1是最低......
  • [题解]CF1748C Zero-Sum Prefixes
    UPD23.10.3更新的对思路的描述,以及代码。思路对于每一个\(a_i=0\),如果我们将它变为\(x\),都可以直接将\(i\simn\)位置上的前缀和加\(x\)。设\(a_j\)是\(a_i\)后第一个\(0\),那么,在\(j\)时同样有上述规律。所以,我们只需在\(i\)时考虑,\(i\sim(j-1)\)的贡......
  • HDU 5834 Magic boy Bi Luo with his excited tree
    题意:给出一棵\(n\)个节点的树,树上每一个节点都有一个权值\(v\),每条边都有一个代价\(w\),从一个点出发,经过一个点可以得到等同于其点权的收益,经过一个点可以得到等同于其点权的收益,经过一条边可以得到等同于其权值的代价,点权只会获得一次,但是代价会花费多次。对于每个点,询问从这个......
  • 什么是 Angular Tree Shaking 优化机制
    TreeShaking(树摇)是一种在现代JavaScript开发中广泛使用的优化技术,它的目标是消除未使用的代码,以减小应用程序的文件体积。TreeShaking的概念和实现是在JavaScript生态系统中非常重要的一部分,尤其是在构建工具如Webpack和Rollup中。TreeShaking的背景知识为了更好地理解......
  • 题解 [蓝桥杯 2016 省 B] 交换瓶子
    题目链接本题解讲解环图的做法。要将一个\(1\simn\)的排列通过交换变成\(1\simn\),可以先将\(i\)向\(a_i\)连边,那么最终一定会练成若干个环(每个点只有一个出度,也只有一个入度)。假设交换在同一个环中的节点,一个环显然会变成两个环,也就是说,交换一次最多增加一个环的数量,......
  • 【题解】洛谷 P1003 [NOIP2011 提高组] 铺地毯
    原题链接解题思路如果直接按照题意开一个二维数组来模拟每个点最上面的地毯编号,会发现所占空间最坏情况下约为(2*105)2*4B=4*1010*4B=1.6*1011B≈149GB,程序完全无法运行。但实际上没有必要将每一个点的信息记录下来,只需要记录每一块地毯能覆盖哪些点,再依次判断哪那些地毯可以......