[Go to site: main page, start]
Scribd
Upload
9 views2 pages

EJOI 2024 Day 1: Many Pairs Problem

The document outlines a programming task for the European Junior Olympiad in Informatics 2024, where participants must calculate the maximum profit a prince can obtain from trading treaties in a tree-structured kingdom of cities. Each city can be designated as the prince's headquarters, and he can choose up to two neighboring cities to govern, with profit derived from treaties involving those cities. The input consists of city connections and treaty details, and the output should be the maximum profit for each city as headquarters.

Uploaded by

gorgynotfound305
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

EJOI 2024 Day 1: Many Pairs Problem

The document outlines a programming task for the European Junior Olympiad in Informatics 2024, where participants must calculate the maximum profit a prince can obtain from trading treaties in a tree-structured kingdom of cities. Each city can be designated as the prince's headquarters, and he can choose up to two neighboring cities to govern, with profit derived from treaties involving those cities. The input consists of city connections and treaty details, and the output should be the maximum profit for each city as headquarters.

Uploaded by

gorgynotfound305
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

EJOI 2024 Day 1 Day 1 Task

European Junior Olympiad in Informatics 2024 manypairs


Chisinau, Moldova English (ISC)

Many Pairs
EJOI-land is a kingdom consisting of N cities. Each city has a unique index between 1 and N
associated with it. The cities are connected by N − 1 bidirectional roads. It is also guaranteed that
you can reach any city from any other city. In other words, EJOI-land has a tree-like structure.
There are also K trading treaties in EJOI-land. Each treaty is defined by a pair of cities (A, B) and
has cost C associated with it.

The king decided to test his son's governing abilities as follows:

He will choose a city H and designate it as the prince's headquarters. Suppose that the tree
will now be rooted in H .
The prince will choose at most two cities that are neighbours of H . Now H and the subtrees
of the chosen cities are under his governance.

The profit he gets is equal to the sum of the costs C of the treaties under his jurisdiction, for a
treaty to be under his jurisdiction, both cities associated with it must be under his governance.

The king still hasn't announced which city will be the prince's headquarters, but the prince still
likes to wonder. Thus, for each city, he wonders what is the maximal profit he can get if it were to
be chosen as the new headquarters.

Your task is to find the maximal profit for each city.

Input

The first line of input contains two space-separated integers, N and K , the number of cities in
EJOI-land, and the number of trading treaties, respectively.

The following N − 1 lines, each, contain two space-separated integers U and V , meaning that
there is road between cities U and V .

The following K lines, each, contain three space-separated integers A, B , and C - being the two
cities involved in the treaty, and its cost, respectively.

Output

Output N space-separated integers, the i -th integer representing the maximal profit obtainable if
city i were to be chosen as the prince's headquarters.

manypairs (1 of 2)
Example

Input Output

64
62
25
36
12
51 51 51 51 51 33
46
2 5 11
5 6 16
4 3 18
236

With the 6th city as the headquarters, the prince has three ways of choosing the two neighbouring
cities and their respective subtrees:

Cities 2 and 3
Cities 2 and 4
Cities 3 and 4

By choosing to govern over cities 2 and 3, the prince gets the treaties 1, 2, and 4 under his
jurisdiction. Thus, he gets the profit 11 + 16 + 6 = 33.

Constraints and Scoring


2 ≤ N , K ≤ 2 ⋅ 105 .
1 ≤ U , V , A, B ≤ N
1 ≤ C ≤ 106

Your solution will be tested on a set of test groups, each worth a number of points. Each test
group contains a set of test cases. To get the points for a test group, you need to solve all test
cases in the test group.

Group Score Limits

1 12 N , K ≤ 50
2 13 N ≤ 5000, K ≤ 500
3 17 N ≤ 5000, K ≤ 2000
4 21 N , K ≤ 5000
5 37 No further constraints

manypairs (2 of 2)

You might also like