题目名称	2331. [HZOI 2016]仲夏之夜
输入输出	`summer.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	哒哒哒哒哒！于2016-06-11加入
开放分组	全部用户
提交状态
分类标签	HZOI 图论最小生成树
	分享题解

通过：77，提交：153，通过率：50.33%
LCWhiStLe	100	0.045 s	1.10 MiB	C++
‎MistyEye	100	0.104 s	2.22 MiB	C++
Sky_miner	100	0.109 s	191.02 MiB	C++
面对疾风吧疾风疾风吧	100	0.115 s	1.55 MiB	C++
liu_runda	100	0.119 s	2.20 MiB	C++
Sky_miner	100	0.120 s	152.82 MiB	C++
liu_runda	100	0.121 s	2.20 MiB	C++
┭┮﹏┭┮	100	0.121 s	5.35 MiB	C++
金身人面兽	100	0.130 s	1.82 MiB	C++
liu_runda	100	0.130 s	2.20 MiB	C++

关于仲夏之夜的近10条评论(全部评论)
AntiLeaf 2017-05-25 16:00 14楼
long long long long long long long long long lnog lnogn logn logn lgno nlgnogn lgnoglong lonag lolng lnog long long long long long long long long long long long long long lnog olojng long 面对疾风吧疾风疾风吧 2016-07-12 13:54 13楼
还要开longlong保存中间值，，，，中间值 Magic_Sheep 2016-07-06 11:34 12楼
`for(int i=1,x,y;i<n;i++){ scanf("%d%d",&x,&y); if(e[x].ls) e[x].rs=y; else e[x].ls=y; }` SOBER GOOD BOY 2016-06-12 17:40 11楼
回复 @_1370733528 : 楼上的楼上比楼上的楼上的楼上有过之而无不及 Hzoi_ 2016-06-11 20:23 10楼
Bromidic 2016-06-11 20:09 9楼
...要和谐,和谐洛克索耶夫 2016-06-11 19:49 8楼
但楼上评论装逼狗忽略了一个重要的事实：你为了装逼，写评论用了21.1s，而我虽然晚写20s但我只写了1s，所以我总用时你少 0.1s _Itachi 2016-06-11 19:42 7楼
回复 @(无定义) : 讲道理我的评论早发了20s啊TAT liu_runda 2016-06-11 19:34 6楼
回复 @超級賽亞人: 惊现神预言 =_=# 分秒不差一直按F5，结果同时刷新出两条神评论 Orz rvalue 2016-06-11 17:08 5楼

2331. [HZOI 2016]仲夏之夜

★ 输入文件：summer.in 输出文件：summer.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

“一闪一闪亮晶晶，满天都是小星星”，夏天的夜晚，满天繁星。Pty和xx躺在软绵绵的草坪上，仰望这美丽的星空（如下图），让人引起无限的遐想！

Pty开始展开他的想象力：在这片绚丽的星空图上，有n颗星星，从1到n进行编号。现在有n-1条星际航道（双向）把这n颗星星给连接了起来。每条星际航道都有一个过路费（费用是正整数），设这n-1条航道的过路费之和是V。Pty想让每两个星星之间都连一条星际航道，但是要求

在连完之后:

对于任意一种能把n颗星星连接起来的m条航道（这m条航道和现存的航道不完全相同），满足这m条航道的过路费之和>V。

请你告诉Pty：能满足他条件的方案里：图中所有的星级航道过路费之和最小是多少？

Pty将告诉你：这n-1条航道所连接的点，和每条航道的过路费。

例：

N=4时，下图为某个图的n-1条航道及过路费：

那么此图的所有星级航道的过路费之和最小为：17（如下图）

【输入格式】

输入文件summer.in包含n行：

第1行是整数n，表示星际图星星的个数。

接下来共n-1行描述这个图的n-1条航道：

每行3个整数：v,u,t表示这条星际航道连接v,u两颗星星，它的过路费是t。

【输出格式】

输出文件summer.out包含1行:

M（整个图的最小的星级航道过路费之和）

【样例输入】

4

1 2 1

2 4 2

3 4 3

【样例输出】

【提示】

30%的数据满足：1<=n<=100

70%的数据满足：1<=n<=30000

100%的数据满足：1<=n<=100000，t<=100

【来源】

HZOI 2016