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.
Problems
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
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