TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3119
  • Problem
  • P3119[CF566C] 巨人供血 Logistical Questions
    Limits : Time Limit : 10000 MS   Memory Limit : 262144 KB  SPJ
    Judgment Tips : 1s,256MB
    Description

    巨人nodgd由 \(n\) 个器官组成,器官之间用 \(n-1\) 条双向血管相连。连接器官 \(a_i,b_i\) 的血管,长度 \(l_i\) 公里。

    巨人nodgd的某个器官是心脏,心脏负责给其他器官供血。第 \(i\) 个器官需要 \(w_i\) 吨血液,如果沿血管到心脏的距离为 \(t_i\) ,需要消耗 \(w_i\cdot t_i^{1.5}\) 的能量供血。

    虽然你不知道巨人nodgd的心脏究竟是哪个器官,但你知道nodgd的一定位于供血消耗能量最少的地方。那么问题来了,nodgd的心脏在哪呢?供血消耗多少能量呢?

    Input Format

    第一行一个整数 \(n(1\leq n\leq 2\cdot10^5)\) ,器官的数量。

    第二行有 \(n\) 个整数 \(w_1,w_2,\cdots,w_n(0\leq w_i\leq 10^8)\) ,每个器官消耗的血液。

    接下来 \(n-1\) 行,每行三个整数 \(a_i,b_i,l_i(1\leq a_i,b_i\leq n,\ a_i\neq b_i,\ 1\leq l_i\leq 1000)\) ,表示一条双向血管。

    Output Format

    输出一行用空格间隔的两个数,第一个数 \(f\) 是个整数,即心脏的节点编号;第二个数 \(c\) 是个浮点数,即心脏供血消耗的能量。

    当使用你答案中的 \(f\) 计算出的供血耗能,和你答案中的 \(c\) ,都与正确答案的绝对误差或者相对误差不超过 $10^{-6}$ 时,会被判定为正确答案。

    Sample Input

    样例输入1:
    5
    3 1 2 6 5
    1 2 3
    2 3 1
    4 3 9
    5 3 1

    样例输入2:
    2
    5 5
    1 2 2

    Sample Output

    样例输出1:
    3 192.0

    样例输出2:
    1 14.142135623730951000


    Source  CF566C nodgd搬运并提供数据