[Solution] Infected Tree Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Infected Tree Codeforces Solution | Codeforces Problem Solution 2022

C. Infected Tree

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Byteland is a beautiful land known because of its beautiful trees.

Misha has found a binary tree with n$n$ vertices, numbered from 1$1$ to n$n$. A binary tree is an acyclic connected bidirectional graph containing n$n$ vertices and n−1$n-1$ edges. Each vertex has a degree at most 3$3$, whereas the root is the vertex with the number 1$1$ and it has a degree at most 2$2$.

Unfortunately, the root got infected.

The following process happens n$n$ times:

• Misha either chooses a non-infected (and not deleted) vertex and deletes it with all edges which have an end in this vertex or just does nothing.
• Then, the infection spreads to each vertex that is connected by an edge to an already infected vertex (all already infected vertices remain infected).

Solution Click Below:-  CLICK HERE

As Misha does not have much time to think, please tell him what is the maximum number of vertices he can save from the infection (note that deleted vertices are not counted as saved).

Input

There are several test cases in the input data. The first line contains a single integer t$t$ (1≤t≤5000$1\le t\le 5000$) — the number of test cases. This is followed by the test cases description.

Infected Tree Codeforces Solution

Lex String Codeforces Solution

Mystic Permutation Codeforces Solution 

Lena and Matrix Codeforces Solution

ANDfinity Codeforces Solution

The first line of each test case contains one integer n$n$ (2≤n≤3⋅105$2\le n\le 3\cdot {10}^5$) — the number of vertices of the tree.

The i$i$-th of the following n−1$n-1$ lines in the test case contains two positive integers ui$u_i$ and vi$v_i$ (1≤ui,vi≤n$1\le u_i,v_i\le n$), meaning that there exists an edge between them in the graph.

It is guaranteed that the graph is a binary tree rooted at 1$1$. It is also guaranteed that the sum of n$n$ over all test cases won't exceed 3⋅105$3\cdot {10}^5$.

Output

For each test case, output the maximum number of vertices Misha can save.