当前位置: 首页 > news >正文

付费阅读插件wordpress/太原关键词优化公司

付费阅读插件wordpress,太原关键词优化公司,动态ip做网站可以备案吗,河南省住房和城乡建设厅官网查询题目:题目链接 题目大意 题目描述 给定一棵树,它的每个点都有对应的权值。 定义颜色x的同色子图为图中所有颜色为x的边,及其顶点形成的同色子图。 一个同色连通块的权值为该连通块所包含的点的权值的和。 一个同色子图的权值定义为子图内…

题目:题目链接

题目大意

题目描述

给定一棵树,它的每个点都有对应的权值。

定义颜色x的同色子图为图中所有颜色为x的边,及其顶点形成的同色子图。

一个同色连通块的权值为该连通块所包含的点的权值的和。

一个同色子图的权值定义为子图内所有同色连通块的权值的最大值。

一种染色方案的权值定义为所有颜色的同色子图的权值和。

输入格式

在输入的第一行中,有一个整数t(1≤t≤1e5)表示测试用例的数量。然后是t组测试用例。

每个测试用例的第一行包含一个整数n(2≤n≤1e5)。第二行由n个整数 w1,w2,…,wn(0≤wi≤1e9)组成,wi等于第i个顶点的权重。在以下n−1行的每一行中,有两个整数u、v(1≤u,v≤n)描述顶点u和v之间的边。并且保证这些边形能够成树。

所有测试用例中n的总和将不超过2e5。

输出格式

对于每个测试用例,你的程序应该打印一行包含n−1个整数的行,用一个空格分隔。一行中的第i个数字应该是树的第i个着色的最大值。

测试样例

输入样例:

4
4
3 5 4 6
2 1
3 1
4 3
2
21 32
2 1
6
20 13 17 13 13 11
2 1
3 1
4 1
5 1
6 1
4
10 6 6 6
1 2
2 3
4 1

输出样例:

18 22 25
53
87 107 127 147 167
28 38 44

题目分析

        这个题目要求的是第i次染色后,树的权值的最大值,因为相同颜色的子图的总权值为权值最大那个子图的权值,而其余与它颜色相同的子图的权值便被忽略不计。根据贪心思想,我们应当尽可能多的使用颜色,即让每个颜色仅有一个子图

        关于图的权值的变化,我们发现,若是我们将一个段分成两个颜色不同的子段,那么这两个子段相交处的那个点的权值便会被算两次,即图的总权值会在原有的基础上加上那个交点的权值(就像题目Note中从第一步到第二步那样)。因此我们每次将可用的点中权值最大的那个点作为交点即可求出最大的权值。

        注意,图中的叶节点(仅连有一条边的点)不可作为交点,否则其将图分为一个子图和一个空图,总权值不变。而一个连了i条边的点最多可以作i-1次交点。

代码

#include<bits/stdc++.h>
using namespace std;struct Node {int w,num;//w为该点权值,num为该点所连边数,num-1为可作交点的次数bool operator<(const Node &x) const {return w > x.w;//重载小于号}
};
Node p[100005];
int t,n;int main() {int v,u;ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>t;while (t--) {long long ans=0;cin>>n;for (int i=1;i<=n;i++)cin>>p[i].w,p[i].num=0,ans+=p[i].w;for (int i=1;i<n;i++) {cin>>u>>v;p[v].num++;p[u].num++;}sort(p+1,p+n+1);//让权值大的排在前面cout<<ans<<' ';int cnt=1;while (cnt<=n) {if (p[cnt].num>1) {//确保该点不是叶节点且作交点次数没超限制p[cnt].num--;//将该点作交点的机会数减一ans+=p[cnt].w;cout<<ans<<' ';}else cnt++;}cout<<endl;}
}

http://www.whsansanxincailiao.cn/news/32016666.html

相关文章:

  • 落地页网站建设/b站推广网站入口
  • 做h5单页的网站/seo求职信息
  • 做720效果的还有哪个网站/广州百度竞价外包
  • 石家庄常规网站建设私人定做/网站推广应该坚持什么策略
  • 做英文简历的网站/网址大全浏览器
  • 十堰做网站最专业的公司/键词优化排名
  • 江西学校网站建设/竞价排名
  • 深圳精品网站制作/百度手机版
  • 网站开发中遇到哪些问题/竞价托管
  • 谷歌独立站建站公司/中国职业培训在线官网
  • 凤岗镇仿做网站/免费企业黄页查询官网
  • 张掖网站建设培训班/沧州做网络推广的平台
  • 兰州有互联网公司嘛/湖南seo服务
  • 厚街找人做网站/广州疫情最新数据
  • web网站开发技术说明/怎么营销一个产品
  • 巴中市建设局网站/网络营销怎么做
  • 做网站麻烦么/网址域名ip解析
  • 做qq头像的网站/口碑营销案例简短
  • 做网站发广告/广告主资源哪里找
  • 需要做网站建设的公司/企业seo案例
  • 诸塈市建设局网站/网推是什么
  • 装修网站建设优缺点/辅导班培训机构
  • 淘宝店做网站建设不能开直通车/短视频培训要多少学费
  • 南昌做网站的公司有哪些/竞价广告推广
  • 在线兼容测试网站/百度招商加盟推广
  • 域名解析后网站怎么建设/自媒体有哪些平台
  • 自己建设网站的利弊/百度seo新站优化
  • 网站服务器租用一般费用/建立网站需要多少钱
  • 南京网站设计开发/山东网页定制
  • 上海各区的网站有哪些公司/网络营销活动案例