IT Restaurants

题意翻译

## 题目描述： 给定一个n，表示有n个节点（1～n）以及接下来n-1条边的树，现用两种颜色（红，蓝）对这颗树的节点染色，染色规则是，每个节点有三种状态，要么染成红色，要么染成蓝色，要么不染色，并且规定用一条边连接的两个节点要么染成颜色相同，要么一个染色一个不染色。问在保证染色节点最多的条件下，红色与蓝色的个数的情况。（要求是至少有一个节点被染成红色，至少一个节点被染成蓝色）。 ## 输入输出格式： #### 输入格式： 第一行一个n，接下来n行每行两个数，表示一条无向边。 #### 输出格式： 第一行输出一个数表示可行方案数。 接下来若干行每行输出两个数表示染成红色的数量和染成蓝色的数量。（按红的数量的升序输出）。

题目描述

Сity N. has a huge problem with roads, food and IT-infrastructure. In total the city has $ n $ junctions, some pairs of them are connected by bidirectional roads. The road network consists of $ n-1 $ roads, you can get from any junction to any other one by these roads. Yes, you're right — the road network forms an undirected tree. Recently, the Mayor came up with a way that eliminates the problems with the food and the IT-infrastructure at the same time! He decided to put at the city junctions restaurants of two well-known cafe networks for IT professionals: "iMac D0naldz" and "Burger Bing". Since the network owners are not friends, it is strictly prohibited to place two restaurants of different networks on neighboring junctions. There are other requirements. Here's the full list: - each junction must have at most one restaurant; - each restaurant belongs either to "iMac D0naldz", or to "Burger Bing"; - each network should build at least one restaurant; - there is no pair of junctions that are connected by a road and contains restaurants of different networks. The Mayor is going to take a large tax from each restaurant, so he is interested in making the total number of the restaurants as large as possible. Help the Mayor to analyze the situation. Find all such pairs of $ (a,b) $ that $ a $ restaurants can belong to "iMac D0naldz", $ b $ restaurants can belong to "Burger Bing", and the sum of $ a+b $ is as large as possible.

输入输出格式

输入格式

The first input line contains integer $ n $ $ (3<=n<=5000) $ — the number of junctions in the city. Next $ n-1 $ lines list all roads one per line. Each road is given as a pair of integers $ x_{i},y_{i} $ $ (1<=x_{i},y_{i}<=n) $ — the indexes of connected junctions. Consider the junctions indexed from 1 to $ n $ . It is guaranteed that the given road network is represented by an undirected tree with $ n $ vertexes.

输出格式

Print on the first line integer $ z $ — the number of sought pairs. Then print all sought pairs $ (a,b) $ in the order of increasing of the first component $ a $ .

输入输出样例

输入样例 #1

5
1 2
2 3
3 4
4 5

输出样例 #1

3
1 3
2 2
3 1

输入样例 #2

10
1 2
2 3
3 4
5 6
6 7
7 4
8 9
9 10
10 4

输出样例 #2

6
1 8
2 7
3 6
6 3
7 2
8 1

说明

The figure below shows the answers to the first test case. The junctions with "iMac D0naldz" restaurants are marked red and "Burger Bing" restaurants are marked blue.