Tidke In Trouble

All submissions for this problem are available.
Once upon a time, there existed a kingdom called Buzzland. Since Buzzland was too large, the emperor of this kingdom, Lord Shivam Balikondwar III could not solve the administration problem. So he hired up, the greatest empire planner of that time, Shubham Tidke. Tidke suggested the empire can be divided into $N$ cities and $N  1$ bidirectional roads connecting the cities to every city. The Emperor trusted Tidke and began the construction of roads. To ensure proper construction is being done, Tidke assigned a integer between 1 to 100 to every road of the kingdom depending on how much construction was done till that time. It represents the amount of work done in percentage. Now, Lord Shivam suddenly felt he should check the construction process! Lord Shivam can choose a city at random. Let's say, he chose city $X$. Then he would travel from city $X$ to every other city in his empire. After choosing a city $X$, for every other city $Y$, consider that he is inspecting the roads on the path from city $X$ to city $Y$, if he finds the construction done of two adjacent roads along this path is same, he will punish Tidke! You, on the other hand, are Tidke's best friend. You don't want him to get punished. So you suggest Lord Shivam a set of cities of size $M$, such that Lord Shivam can choose any city from this set without getting Tidke punished. Also, let's say that if the set consists of more than one city, for any two cities of this set, $X$ and $Y$, the path between these two cities contains cities from the this set only! The path between the cities $X$ and $Y$ ($X$ and $Y$ belonging to a set), should not contain a city which is not present in the respective set. You don't have to print the set. Just print maximum size of that set which will help you to save Tidke. ###Input:  First line will contain $T$, number of testcases. Then the testcases follow.  For every testcase, first line contains number of cities $N$  Next $N  1$ lines follow three space separated integers $X$ $Y$ $C$, denoting there exists a road between cities $X$ and $Y$ and the integer assigned to it. ###Output: For each testcase, output the maximum size of possible set of cities. ###Constraints  $1 \leq T \leq 10$  $1 \leq N \leq 10^5$  $1 \leq C \leq 100$ ###Sample Input: 2 6 1 2 10 2 3 10 2 4 20 4 5 40 4 6 30 4 1 2 10 2 3 10 3 4 10 ###Sample Output: 4 0 ###Explanation: testcase1 : The sets which satisfy given condition are {2},{4},{5},{6},{2,4},{4,6},{4,5},{2,4,5},{2,4,6},{5,4,6},{2,4,5,6}. Maximum size is 4. testcase 2: any city chosen leads to Tidke getting punished.Author:  buzz_95 
Tags  buzz_95 
Date Added:  15082019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions