← 返回题目列表

Codeforces · 1939/B

B. 证据板

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Evidence Board - 原题 PDF 第 1 页
原题PDF第6页
Evidence Board - 原题 PDF 第 2 页
原题PDF第7页
Evidence Board - 原题 PDF 第 3 页
原题PDF第8页
可复制的 PDF 提取文本
XVIII Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules)
                                       Russia, Moscow, March, 8, 2024
Problem B. Evidence Board

     Input file:         standard input
    Output file:       standard output
    Time limit:        2 seconds
    Memory limit:     512 megabytes

Volodya dreams of becoming a detective. Therefore, Volodya often reads books that tell incredible stories
of solving crimes. Studying the next case, Volodya came across interesting details of the investigation.

There were a total of n suspected persons in the case. The evidence board contains all n persons. Initially,
there were no connections between them.

During the investigation, new connections between suspected persons emerged one after another. Each
connection linked two persons that previously had no connection with each other, even indirectly through
several other persons.

Let’s consider what happened when a connection between persons A and B emerged. In addition to the
names of the persons, each connection had three parameters: cA — the strength of the evidence against A,
cB — the strength of the evidence against B, and wAB — the total strength of the evidence of connection.
For natural reasons, the strength of the evidence of connection could not exceed the sum of strengths of the
evidence against A and B. That means that for each connection, it was necessarily that wAB ≤cA +cB.
Upon receiving such connection, the detectives drew a line on the board between the images of persons
A and B, assigning the wAB to this line. Also, a sticker with the number cA was placed on the image of
person A, and a sticker with the number cB was placed on B. If there were already other stickers on the
image, the new sticker was placed on top of the old ones.

The case was solved exactly at the moment when all the suspected persons were linked through n −1
connections. After solving the crime, the board was placed in the museum in its original form.

Inspired by this approach, Volodya visited that museum and studied the evidence board in detail.
Volodya noticed that the image of person v contained stickers with numbers cv,1, . . . , cv,degv numbered
from top to bottom. Here, degv denotes the number of connections associated with person v. Also,
Volodya remembered that the i-th connection was between persons ai and bi and had evidence strength
wi. Unfortunately the connections were arbitrarily numbered, and their numbers did not necessarily
correspond to the order in which they appeared during the investigation.

Due to the confusion with the numbers of connections, the information on the board did not help to
restore the process of the investigation. Now Volodya needs to restore any possible chronological order in
which the connections could have emerged for the detectives. This task is too difficult for him, so he asks
your help. It is also possible that the museum falsified information, and a suitable order does not exist.

Input

The first line of the input contains two integers n and g (2 ≤n ≤200 000, 0 ≤g ≤9) — the number of
suspected persons in the case and the test group number.

The next n −1 lines describe the connections. The i-th line contains three integers ai,  bi, and wi
(1 ≤ai, bi ≤n, 1 ≤wi ≤109, ai ̸= bi) — the persons connected by the i-th connection and the
total strength of the i-th connection. It is guaranteed that connections link all persons together.

The next n lines describe the numbers written on the stickers. The i-th line contains degi integers
ci,1, . . . , ci,degi (0 ≤ci,j ≤109) — the numbers written on the stickers on the image of the i-th person from
top to bottom. degi equals the number of connections associated with person i.

Output

If there is no suitable chronological order for the restoration of connections according to the conditions of
the problem, output “No” (without quotes) on a single line.

Otherwise, on the first line output “Yes” (without quotes). On the second line, output n −1 numbers — a



                                         Page 6 of 12

XVIII Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules)
                                       Russia, Moscow, March, 8, 2024

suitable chronological order of connections to emerge. The connections are numbered from 1 to n −1 in
the same order as they are given in the input. If there are multiple possible orders, output any of them.

Examples

             standard input                          standard output
 5 0                                     Yes
 1 2 3                                   1 4 2 3
 1 3 1
 3 4 12
 3 5 6
 0 4
 2
 6 1 3
 8
 3

 7 0                                     Yes
 1 2 4                                   5 1 2 3 6 4
 2 3 4
 3 4 4
 4 5 4
 5 6 4
 6 7 4
 2
 1 2
 2 3
 1 2
 3 2
 1 2
 179

 4 0                                     No
 1 2 7
 1 3 6
 1 4 5
 3 2 1
 5
 4
 3

Note

In the first example, one of the possible orders is [1, 4, 2, 3]. In chronological order, the first connection
links A = 1 and B = 2, cA = 4, cB = 2, wAB = 3, 3 ≤2 + 4 — the evidence is correct. The second
connection links A = 3 and B = 5, cA = 3, cB = 3, wAB = 6, 6 ≤3 + 3 — the evidence is correct. The
third connection links A = 1 and B = 3, cA = 0, cB = 1, wAB = 1, 1 ≤0 + 1 — the evidence is correct.
The fourth connection links A = 3 and B = 4, cA = 6, cB = 8, wAB = 12, 12 ≤6 + 8 – the evidence is
correct. For a better understanding, refer to the illustration.





                                         Page 7 of 12

XVIII Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules)
                                       Russia, Moscow, March, 8, 2024





Scoring

The tests for this problem consist of nine groups. Points for each group are given only if all tests of the
group and all tests of the required groups are passed. Please note that passing the example tests is not
required for some groups. Offline-evaluation means that the results of testing your solution on this
group will only be available after the end of the competition.


                               Additional constraints             Required
  Group  Points                                                 Comment
                                                          Groups                  n                     ai, bi, ci, wi

     0       0        –                    –                    –          Examples.

     1      10    n ≤10                  –                    0              –

     2      15       –             ai = i, bi = i + 1 for all i          –              –

     3       8        –             ai = 1, bi = i + 1 for all i          –              –

     4       9        –             ai ≤2, bi = i + 1 for all i          3              –

     5       7    n ≤1000     ci,1 ≤ci,2 ≤. . . ≤ci,degi for all i       –              –

     6       7    n ≤1000    ci,j = 0 for all 1 ≤i ≤n and j ≥2      –              –
                                      n  degv      n−1
     7      17       –    X X cv,i = X wi            –              –
                                     v=1 i=1       i=1
     8      16   n ≤1000                 –                      0, 1, 5, 6           –

     9      11       –                    –                   0 – 8    Offline-evaluation





                                         Page 8 of 12