E. IT Restaurants

链接：https://www.luogu.com.cn/problem/CF212E
https://codeforces.com/problemset/problem/212/E
题目：

思路：
首先题目说要保证最大的数量，并且每个颜色的点至少有一个，那么很显然染色的点有n-1个，且唯一没染色的点必须有两个及以上的子节点
我们这样去理解没染色的点：它的子节点颜色可以不一样，但是它的子节点为根节点的子树颜色必须一样，所以理解为转色点。

如果1不染色，那么子树的节点数量是3 3 1所以红色的节点数可以且仅可以是1 3 4 6
那么对每个非叶子节点进行分析即可。
主要是01背包的部分编码有点怪？
代码：

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;
const int N = 5e3 + 10;
vector<int>G[N];
bool vis[N];
void dfs(int u, int& nums)
{
	vis[u] = 1; nums++;
	for (int v : G[u])
	{
		if (!vis[v])
		{
			dfs(v, nums);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n-1; i++)
	{
		int u, v; cin >> u >> v;
		G[u].push_back(v), G[v].push_back(u);
	}
	map<int,bool>red;
	for (int i = 1; i <= n; i++)
	{
		if (G[i].size() == 1)continue;//叶子节点直接跳
		memset(vis, 0, sizeof(vis));
		vis[i] = 1;//用来写dfs
		vector<int>child;
		child.push_back(0);//每颗子树的节点数，为了方便从1开始，首先push_back一个0
		for (int u : G[i])
		{
			int nums = 0;
			dfs(u, nums);
			child.push_back(nums);
		}
		vector<int>dp;//当前的背包空间
		int childlength = child.size();//固定长度
		map<int,bool>mpr;//判断有没有出现，局部map
		for(int j=1;j<=childlength-1;j++)
		{
			bool isgo = false;
			if (!mpr[child[j]])
			{
				if (!red[child[j]])red[child[j]] = 1;
				mpr[child[j]] = 1;
				dp.push_back(child[j]);
				isgo = true;//如果塞了新的数进去，那么最后一个不能用
			}
			int length = dp.size();//固定长度
			if (isgo)length--;
			for (int k = 0; k < length; k++)
			{
				if (!mpr[child[j] + dp[k]])//局部
				{
					if (!red[child[j] + dp[k]])red[child[j] + dp[k]] = 1;//总体
					mpr[child[j] + dp[k]] = 1;
					dp.push_back(child[j] + dp[k]);
				}
			}
		}
	}
	red.erase(n-1);//涂掉全是红色的节点，因为至少要有1个蓝色
	cout << red.size() << endl;
	
	for (map<int, bool>::iterator it = red.begin(); it != red.end(); ++it)
	{
		
		cout << it->first << ' ' << n - 1 - it->first << endl;
	}
	return 0;
}