题目链接：https://codeforces.com/contest/212/problem/E
题目大意：

题目大意：给你一个无向树，现在用两种颜色去给这颗树上的节点染色。用（a,b）表示两种颜色分别染的节点数。满足以下条件：
1.任何一种颜色至少使用一次，即a>=1&&b>=1。
2.两种颜色染的节点不能相邻，即不能有边的两端染不同色。要你使a+b值最大下输出不同的（a,b),按照a升序输出。

算法思路：很容易得出一个结论：a+b的最大值就是取n-1，即只有一个点不染色。我们枚举这个不染色的点，那么每一棵子树只能染一种颜色。我们求出所有的子树，跑一个01背包。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
 
vector<int> v[5005];
int sum[5005], tot, f[5005], g[5005];
 
int dfs(int u, int fa, int tot){
    sum[tot]++;
    for(int i=0; i<v[u].size(); i++){
        if(v[u][i]!=fa){
            dfs(v[u][i], u, (fa==-1?++tot:tot));
        }
    }
    return tot;
}
 
int main(){
 
    int n, a, b, ans=0;
    scanf("%d", &n);
    for(int i=1; i<n; i++){
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1; i<=n; i++){
        memset(sum, 0, sizeof(sum));
        memset(f, 0, sizeof(f));
        f[0]=1;
        int tot=dfs(i, -1, 0);
        for(int i=1; i<=tot; i++){
            for(int j=5000; j>=sum[i]; j--){
                f[j]=max(f[j], f[j-sum[i]]);
            }
        }
        if(tot==1){
            continue;
        }
        f[n-1]=0;//每个颜色都必须有
        ans=0;
        for(int j=5000; j>=1; j--){
            g[j]=max(g[j], f[j]);
            ans+=g[j];
        }
    }
    printf("%d\n", ans);
    for(int i=1; i<5000; i++){
        if(g[i]){
            printf("%d %d\n", i, n-i-1);
        }
    }
 
    return 0;
}