问题 A: Leaves [Easy] Solution

题目描述







Write a program to print all the leaves of the given tree, numbered from 1 to N. The root of the tree is node 1.







输入







The first line will be an integer T (1≤T≤10), which is the number of test cases.




For each test data:




The first line contains one integer N (2≤N≤10^4) — the number of the nodes.




Each of the next N - 1 lines contain two integers a and b, which means there is an edge between node a and b (1≤a, b≤N).




输出







For each case please, print all the leaves of the given tree, in ascending order.










For the tree has multiple leaf nodes, there is a blank between two leaf nodes, and ‘\n’ at the end of each line.




样例输入










1




4




2



2 3




3 4




样例输出










4

问题 B: Preinpost [Easy]







题目描述







Write a program to print the pre order, in order and post order traversal of the given binary tree.

输入







The first line will be an integer T (1≤T≤10), which is the number of test cases.




For each test data:




The first line contains one integer N (1≤N≤10^4) — the number of the nodes.




Each of the next N - 1 lines contain two integers a and b, which means node a is the father of node b (1≤a, b≤N). If a node has two sons, the son appeared earlier is the left son and another is the right son. If a node only has one son, the son is the left son.




输出







For each test cases, print three lines: the pre order, in order and post order traversal of the given binary tree.




样例输入










1




8




4



3



4 2




2 7




3 5




3 6




6 8










样例输出










1 4 2 7 3 5 6 8




7 2 4 1 5 3 8 6




7 2 4 5 8 6 3 1

问题 C: Heap [Easy]







题目描述







There is a set with size n initially, and there are q operations, each operation will be one of the following cases:




Add x: add x to this set.




Delete: delete the minimum element of the set.




Query: print the minimum element of the set.




输入







The first line will be an integer T, which is the number of test cases. (1 <= T <= 10).




For each test case, the first line will be an integer n (1 <= n <= 10^5), then the second line will be n integers ai (1<=ai<=10^9), they make up the initial set. The third line will be an integer q (1 <= q <= 10^5), it means the number of operations. Then followed by q lines, each line will be one of the following cases:




1 x: Add x (1<=x<=10^9).




Delete.



Query.



输出







For each “Query”, print the minimum element of the set in a line.




样例输入










1




2




3



 



1 2




3




样例输出










2

问题 D: The largest distance [Medium]







题目描述







Write a program to print the longest distance between two nodes of the given tree.




输入







The first line will be an integer T (1≤T≤10), which is the number of test cases.




For each test data:




The first line contains two integers N (1≤N≤10^5) — the number of the nodes.




Each of the next N - 1 lines contain two integers a and b, which means there is an edge between node a and b.




输出







For each case, please print the longest distance between two nodes of the given tree.




样例输入










1




8




4



3



4 2




2 7




3 5




3 6




6 8




样例输出










6










问题 E: BuyBuyBuy [Medium]

题目描述







Hong came to Qinghuangdao for CCPC Camp this summer. After the camp, Hong decides to buy his friends some gifts.




The capacity of Hong's pocket is so small that it can only contain M gifts. Considering the diversity of his gifts, Hong would not buy two of the same kind. And some typical gift should be chosen to represent the features of Qinghuangdao.




Hong will walk down from north to south and visit N shops one by one along the shopping street. There is ONLY ONE type of gift sold in each shop. However, he has such a poor memory that he can't remember how many shops sell gift K. So, he will write a number L on this gift he bought in his pocket, to indicate how many shops where sell gift K. In Hong's opinion, the smaller the number L is, the better the gift.




When Hong stops in a shop which sells gift K, the following three situations he might come across.




\1. If there is not gift K in his pocket and still some place for it, He will buy without hesitation. Before putting it into the pocket, he will write down the number `1' on the gift to indicate that he has once seen one shop selling it.




\2. If there is gift K in his pocket, he will just replace the number L with L + 1, indicating L + 1 shops sell gift K.




\3. If there is not gift K in his pocket and the pocket is full, he would like to regard no shops selling gift K (because he cannot remember whether he has met gift K), so he will have to discard one gift in his pocket to release a place for the gift K. But which gift should be discarded? According to the follow rule:




He chooses the gift that has the biggest number L on it. If several gifts have the same biggest number L, he will discard the one which has been putted into the pocket at the earliest time. After discarding the gift, he will put gift K into his pocket and write number `1' on gift K.




Now, your task is to write a program to record the number of these gifts which have been discarded by Hong.




输入







The first line will be an integer T (1≤T≤10), which is the number of test cases.




For each test data:




The first line has two positive integers M and N (M<=50000, N<=100000) where M (the capacity of pocket) shows how many gifts it can take, and N is the number of shops in the street. The second line has N positive integers Ki (Ki < 2^20, i = 1, 2, ..., N) indicating the type of gift sold in the i-th shop.




输出







For each test case you should output one integer, the number of discarded gifts as indicated in the sample output.




样例输入










6




3 5

1 2 3 2 4



2 4




1 2 2 1




2 6




1 2 2 1 1024 1




2 10




1 2 3 2 4 2 3 6 7 8




1



1048575




6 16




10 1 2 3 4 5 6 1 2 3 6 5 4 10 1 6










样例输出










1




0




2




7




0




3




问题 F: Game [Hard]







题目描述







Hong likes game very much. He wants to play a game with you.




There is a tree with N nodes. Node 1 is the root. Each node is colored black or white.




Each turn, the player should choose a black node and change it to white. After that, he can choose its any number of the proper ancestors and change their color. The one who cannot find a black node at the tree in his turn, he lose the game.




Hong is good at the game, so he let you take the first turn. Hong will always find the optimal solution. He wants to know if you can win the game.




输入







The first line will be an integer T (1≤T≤100), which is the number of test cases.




For each test data:

The first line contains one integer N (1≤N≤10000) — the number of the nodes.




The second line contains N integers w1…wn {0, 1}, wi = 1 means node i is black. Otherwise node i is white.




Each of the next N - 1 lines contain two integers a and b, which means there is an edge between node a and b.




输出







For each teat case, if you can win, print “YES”; Otherwise, print “NO”.




样例输入










1




2




0



2



样例输出










YES










问题 G: Hong set [Hard]







题目描述







Hong has a tree, whose vertices are conveniently labeled by 1, 2, ..., n. Each node has a weight wi.




A set with m nodes v1, v2, ..., vm is a Hong Set if:




The rest of his tree induced by this set is connected.



After we sort these nodes in set by their weights in ascending order, we get u1, u2, ..., um, (that is, wui < wui+1 for i from 1 to m-1). For any node x in the path from uito ui+1(excluding ui and ui+1), should satisfy wx < wui.



Your task is to find the maximum size of Hong Set in a given tree.




输入









The first line will be an integer T (1≤T≤10), which is the number of test cases.




For each test data:



The first line contains two integers N (1≤N≤200000) — the number of the nodes.




The second line contains N integers w1…wn (1<=wi<=10^9).




Each of the next N - 1 lines contain two integers a and b, which means there is an edge between node a and b.




输出







For each case please print the maximum size of Hong Set.




样例输入










1




7




3 30 350 100 200 300 400




2



2 3




3 4




4 5




5 6




6 7




样例输出










5