Codeforces Round 1045 (Div. 2)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
2134 Codeforces Round 1045 (Div. 2) FINISHED False 7200 20186723 Aug. 26, 2025, 2:35 p.m.

Problems

Solved
Index
Name
Type
Tags
Community Tag
Rating
( 3624 ) D Sliding Tree PROGRAMMING constructive algorithms dfs and similar trees

You are given a tree(^{\text{∗}}) with (n) vertices numbered from (1) to (n). You can modify its structure using the following multi-step operation, called a sliding operation : Choose three distinct vertices (a), (b), and (c) such that (b) is directly connected to both (a) and (c). Then, for every neighbor (d) of (b) ( excluding (a) and (c)), remove the edge between (b) and (d), and instead connect (d) directly to (c). For example, the figure below illustrates this operation with (a = 4), (b = 3), and (c = 5) in the leftmost tree. It can be proved that after a sliding operation, the resulting graph is still a tree. Your task is to find a sequence of sliding operations that transforms the tree into a path graph(^{\text{†}}), while minimizing the total number of operations. You only need to output the first sliding operation in an optimal sequence if at least one operation is required. It can be proved that it is possible to transform the tree into a path graph using a finite number of operations. (^{\text{∗}})A tree is a connected graph without cycles. (^{\text{†}})A path graph is a tree where every vertex has a degree of at most (2). Note that a graph with only (1) vertex and no edges is also a path graph. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains a single integer (n) ((1 \le n \le 2 \cdot 10^5)) — the number of vertices in the tree. The (i)-th of the following (n-1) lines contains two integers (u_i) and (v_i) ((1 \le u_i,v_i \le n), (u_i \neq v_i)) — the ends of the (i)-th edge. It is guaranteed that the given edges form a tree. It is guaranteed that the sum of (n) over all test cases does not exceed (2 \cdot 10^5). For each test case: If no oper

Tutorials

145832

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
335711389 og.kostya D Aug. 26, 2025, 5:55 p.m. OK C# 10 TESTS 28 280 31744000
335711598 og.kostya D Aug. 26, 2025, 5:57 p.m. OK C# 13 TESTS 28 406 43212800
335738232 flanky_chrm D Aug. 27, 2025, 1:10 a.m. OK C# 13 TESTS 28 577 92672000
335710764 -firefly- D Aug. 26, 2025, 5:51 p.m. OK C# 13 TESTS 28 1109 89088000

remove filters

Back to search problems