GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Saturday 18 June 2022

[Solution] Tree Queries (Easy Version) Codeforces Solution

D1. Tree Queries (Easy Version)
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
The only difference between this problem and D2 is the bound on the size of the tree.

You are given an unrooted tree with n vertices. There is some hidden vertex x in that tree that you are trying to find.

To do this, you may ask k queries v1,v2,…,vk where the vi are vertices in the tree. After you are finished asking all of the queries, you are given k numbers d1,d2,…,dk, where di is the number of edges on the shortest path between vi and x. Note that you know which distance corresponds to which query.

What is the minimum k such that there exists some queries v1,v2,…,vk that let you always uniquely identify x (no matter what x is).

Solution Click Below:-  CLICK HERE

Note that you don't actually need to output these queries.

Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). Description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤2000)  — the number of vertices in the tree.

Each of the next n−1 lines contains two integers x and y (1≤x,y≤n), meaning there is an edges between vertices x and y in the tree.


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

Output
For each test case print a single nonnegative integer, the minimum number of queries you need, on its own line.

No comments:

Post a Comment