Seacave Jellyfish
本题没有可用的提交语言。
Description
Ao Run, the white dragon among the Dragons of Four Seas and the King of the West Seas (don't ask me which sea that is), has identified an elaborate network of seacaves, labelled $1, \dots, n$, that is connected by exactly $n-1$ bidirectional pathways, represented by the starting and ending seacaves, as well as the amount of energy it takes for him to traverse through that pathway —- all hidden from human intervention in the form of submarines, undersea cables, and other activities that Ao Run views as nuisances. Importantly, the King notices that every cave is reachable from every other cave.
As an avid enjoyer of jellyfish, the King is also flattered to discover that seacave $i$ contains $c_i$ units of jellyfish that he can engage with. But the King is also lazy —- his interest in engaging with the jellyfish is hindered by the amount of energy he must spend to reach these jellyfish. As a result, the total engagement he'll get from the jellyfish from cave $x$ after traveling from cave $y$ is evaluated by $\dfrac{c_x}{dist(x, y) + 1}$, where $dist(x, y)$ is the minimal amount of energy to traverse from cave $x$ to $y$ using the pathways, and $1$ is the energy that the King needs to engage with the jellyfish.
The King, however, still intends to engage with jellyfish from every cave; to do so, he wants to establish a base that maximizes the total engagement —- so you, the King's special advisor, must find the cave such that maximizes the sum of engagement from that cave to all caves (including the current cave), as well as that sum of engagement. Importantly, you may treat the King's engagements as separate - he will engage with the $n$ seacaves of jellyfish separately.
The first line will consist of one integer, $n$ ($2\leq n \leq 100$).
The second line will consist of $n$ integers, $c_i$ ($1\leq i \leq n$, $0\leq c_i \leq 10^9$).
For each of the next $n-1$ lines, the following: $x$, $y$, $w$, denoting a hidden bidirectional pathway between caves $x$ and $y$, with a traversal energy of $w$ ($1\leq x, y \leq n$, $1\leq w\leq 10^3$)
Two lines. The first line contains a single integer, the 1-based index of the seacave that maximizes the sum of engagement from the cave to all caves.
The second line contains the total engagement gained by engaging with jellyfish from all seacaves when the King is based in the seacave you printed in the last line, rounded to 5 digits after the decimal. The judging system will accept answers within $10^{-4}$ from the correct solution.
Input
The first line will consist of one integer, $n$ ($2\leq n \leq 100$).
The second line will consist of $n$ integers, $c_i$ ($1\leq i \leq n$, $0\leq c_i \leq 10^9$).
For each of the next $n-1$ lines, the following: $x$, $y$, $w$, denoting a hidden bidirectional pathway between caves $x$ and $y$, with a traversal energy of $w$ ($1\leq x, y \leq n$, $1\leq w\leq 10^3$)
Output
Two lines. The first line contains a single integer, the 1-based index of the seacave that maximizes the sum of engagement from the cave to all caves.
The second line contains the total engagement gained by engaging with jellyfish from all seacaves when the King is based in the seacave you printed in the last line, rounded to 5 digits after the decimal. The judging system will accept answers within $10^{-4}$ from the correct solution.
5
5 2 9 1 7
1 2 2
1 3 2
3 4 1
3 5 3
3
13.31667
Note
In the sample, when the king is based in seacave 3, he can:
- engage with $9$ units of jellyfish in seacave $3$ using $1$ energy, for an engagement gain of $\dfrac{9}{1} = 9$;
- engage with $5$ units of jellyfish in seacave $1$ using $3$ energy ($2$ for getting from seacave $3$ to $1$, $1$ for the engagement itself), for an engagement gain of $\dfrac{5}{2+1} = \dfrac{5}{3}$;
- engage with $2$ units of jellyfish in seacave $2$ using $2+2+1=5$ energy, for an engagement gain of $\dfrac{2}{5} = 0.4$;
- engage with $7$ units of jellyfish in seacave $5$ using $4$ energy, for an engagement gain of $\dfrac{7}{4} = 1.75$;
- engage with $1$ units of jellyfish in seacave $4$ using $2$ energy, for an engagement gain of $\dfrac{1}{2} = 0.5$;
For a total engagement that sums up to $\dfrac{799}{60}$, or $13.31667$ when rounded.
It can be shown that this is the maximum engagement attainable in this arrangement of seacaves and paths.