


#define OPENSTACK
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int maxn=1e5+;
vector<pair<int,int> > v[maxn];
int c[maxn], cn[maxn], tmp, n;
LL ans; int dfs(int p,int f)
{
int count=;
for(int i=; i<v[p].size(); i++)
{
pair<int,int>pa=v[p][i];
if(pa.first==f) continue; int t=dfs(pa.first,p);
cn[tmp]=min(t,n-t);
ans+=(LL)cn[tmp]*(LL)pa.second;
tmp++;
count+=t;
}
return count+;
} int main()
{
#ifdef OPENSTACK
long long size = << ; // 64MB
char *p = (char*)malloc(size) + size;
#if (defined _WIN64) or (defined __unix)
__asm__("movq %0, %%rsp\n" :: "r"(p));
#else
__asm__("movl %0, %%esp\n" :: "r"(p));
#endif
#endif int T,k; cin>>T;
while(T--)
{
for(int i=;i<maxn;i++) v[i].clear();
scanf("%d%d",&n,&k);
for(int i=;i<n;i++)
{
int u1,u2,w;
scanf("%d%d%d",&u1,&u2,&w);
pair<int,int>pa1=make_pair(u1,w);
pair<int,int>pa2=make_pair(u2,w);
v[u1].push_back(pa2);
v[u2].push_back(pa1);
}
for(int i=;i<k;i++) scanf("%d",&c[i]);
ans=; tmp=;
int res=dfs(,-);
//cout<<"点数-----"<<res<<endl;
//cout<<" -----"<<ans<<endl;
sort(cn,cn+tmp);
sort(c,c+k);
for(int i=tmp-, j=k-; j>=; i--, j--)
{
ans+=(LL)c[j]*(LL)cn[i];
}
printf("%lld\n",ans);
}
#ifdef OPENSTACK
exit();
#else
return ;
#endif
}
“玲珑杯”ACM比赛 Round #18--最后你还是AK了(搜索+思维)的更多相关文章
-
“玲珑杯”ACM比赛 Round #18
“玲珑杯”ACM比赛 Round #18 Start Time:2017-07-15 12:00:00 End Time:2017-07-15 15:46:00 A -- 计算几何你瞎暴力 Time ...
-
“玲珑杯”ACM比赛 Round #18 1147 - 最后你还是AK了(思维,边的贡献)
题目链接:http://www.ifrog.cc/acm/problem/1147 题解:这题很容易想到的是边的贡献也就是每条边最多被取到几次,和点的贡献类似,那些加边只要加在边贡献大的边上就行.然后 ...
-
“玲珑杯”ACM比赛 Round #18 C -- 图论你先敲完模板(和题目一点关系都没有,dp)
题目链接:http://www.ifrog.cc/acm/problem/1146?contest=1020&no=2 题解:显然知道这是一道dp而且 dp[i]=min(dp[j]+2^(x ...
-
玲珑杯”ACM比赛 Round #18 A -- 计算几何你瞎暴力(瞎暴力)
题目链接:http://www.ifrog.cc/acm/problem/1143?contest=1020&no=0 题解:就是瞎暴力具体多暴力看一下代码就知道了. #include < ...
-
“玲珑杯”ACM比赛 Round #18 A 前缀预处理 D dp
DESCRIPTION 今天HHHH 考完了期末考试,他在教学楼里闲逛,他看着教学楼里一间间的教室,于是开始思考: 如果从一个坐标为 (x1,y1,z1)(x1,y1,z1) 的教室走到(x2,y2, ...
-
“玲珑杯”ACM比赛 Round #1
Start Time:2016-08-20 13:00:00 End Time:2016-08-20 18:00:00 Refresh Time:2017-11-12 19:51:52 Public ...
-
“玲珑杯”ACM比赛 Round #12题解&;源码
我能说我比较傻么!就只能做一道签到题,没办法,我就先写下A题的题解&源码吧,日后补上剩余题的题解&源码吧! A ...
-
“玲珑杯”ACM比赛 Round #19题解&;源码【A,规律,B,二分,C,牛顿迭代法,D,平衡树,E,概率dp】
A -- simple math problem Time Limit:2s Memory Limit:128MByte Submissions:1599Solved:270 SAMPLE INPUT ...
-
“玲珑杯”ACM比赛 Round #19 B -- Buildings (RMQ + 二分)
“玲珑杯”ACM比赛 Round #19 Start Time:2017-07-29 14:00:00 End Time:2017-07-29 16:30:00 Refresh Time:2017-0 ...
随机推荐
-
20162311 实验三 敏捷开发与XP实践 实验报告
20162311 实验三 敏捷开发与XP实践 实验报告 实验内容 一.研究学习IDEA中的Code菜单 使用Code ->Reformate Code功能将以下代码格式化 public clas ...
-
css继承属性
在css中我们经常会遇到一些子元素继承父元素的情况 , 有时候不清楚有哪些属性会继承, 在开发中会给我们带来一些麻烦 ,稍作整理还是很有必要. 一.有继承性的属性 1.字体系列属性 font:组合字体 ...
-
yml文件搞一波
引用https://www.cnblogs.com/zslli/p/8717483.html https://www.cnblogs.com/baoyi/p/SpringBoot_YML.html 划 ...
-
AI学习吧-购物车-添加商品接口
create接口流程 需求:向购物车添加商品 流程:写shopping_cart路由--->写ShoppingCart视图函数--->使用Authuser校验用户是否登录--->首先 ...
-
Swagger RESTful API文档规范
*注意编写的关键词:“必须”.“不能”.“需要”.“应当”,“不得”.“应该”.“不应该”,“推荐”.“可能”和“可选的” 原文链接:http://swagger.io/specification/ ...
-
docker 下 alpine 镜像设置时区的有效办法
在使用Docker的时候,由于很多基础linux镜像都比较大,alpine这个仅仅几兆的linux基础镜像受到了很多人喜欢,笔者也不例外,可是由于alpine中的一些配置及命令与常见的centos等系 ...
-
mysql基础知识详解
分享一些mysql数据库的基础知识. 1.每个客户端连接都会从服务器进程中分到一个属于它的线程.而该连接的相应查询都都会通过该线程处理.2.服务器会缓存线程.因此并不会为每个新连接创建或者销毁线程.3 ...
-
zookeeper启动配置
zookeeper安装和配置详解 转载 2014年04月16日 14:36:31 16812 摘自:http://www.ibm.com/developerworks/cn/opensource/os ...
-
flink checkpoint 源码分析 (二)
转发请注明原创地址http://www.cnblogs.com/dongxiao-yang/p/8260370.html flink checkpoint 源码分析 (一)一文主要讲述了在JobMan ...
-
第一百五十五节,封装库--JavaScript,轮播器
封装库--JavaScript,轮播器 html <div id="banner"> <img src="img/banner1.jpg" a ...