Control chain#5229
Rybka decided to determine the criticality of Watson's control network, which consists of nodes connected by conductors. From each node, a signal can be transmitted to any other node only via a unique path.
When an external action is applied to a node, it transmits a signal to every other node. That is, after an external action, the node generates (N-1) signals.
The -node intensity () for a conductor is defined as the product of its length and the number of signals passing through it after an external action on node .
A conductor is said to be -critical if its value is maximal among all conductors for a fixed . In case of equality of , several conductors are considered -critical. The total criticality of a conductor is defined as the number of different for which it is -critical. The criticality of the whole network is the maximum total criticality among all conductors.
The first line contains a single integer — the number of nodes. Next, there are (N-1) lines, each containing three integers , , — describing a conductor that connects nodes and of length .
2 \leq N \leq 10^{5}, 1 \leq i, j \leq N, 1 \leq A \leq 10^{5}.
Print the criticality of the network.
Example 1
In the given network: -critical conductor: ; -critical: ; -critical: ; -critical: ; -critical: .
Therefore, the first conductor has criticalities, so its total criticality is , the total criticality of the other conductors is each, hence, the criticality of the network is .