/ 纪念第一次写树形DP 20201004 9：45.：00 / 题意：给你N个点，n-1条边，形成一棵树，然后每个点可以染红色，蓝色，无色，染红色和染蓝色的数量分别是a,b, 每个点染色规则，相邻的点颜色要么一样，要么一个点染色一个点不染色，至少要染一个红色或者蓝色。问最后a+b最大情况下，a,b的分别的取值
题解：根据题意 我们可以得出，首先要去找到一个根节点的子节点个数，然后以该根节点不染色 ，其他分别染色，然后用背包的思想，详情看代码
#pragma GCC optimize(2) #pragma GCC optimize(3) #include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define mse(a,b) memset(a,b,sizeof a) #define pb push_back using namespace std; const int mod=1e9+7; const int maxx=1e6+10; using namespace std; const long double PI = 3.14159265358979323846; #define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); inline int read() { int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); } while (isdigit(ch)) { x=x*10+ch-48; ch=getchar(); } return x*f;} int dp[5500][6000];///以i为根，凑出j个点 int n; int size[maxx]; ///以i为根的节点个数 bool flag[maxx]; //表示这个棵树是否可以得到i点染红色 vector<int>ans[maxx]; void dfs(int x,int fa){ dp[x][0]=1;///标记当前节点的染色个数 size[x]=1;//初始化根节点 for(int i=0;i<ans[x].size();i++){ int to = ans[x][i]; if(to==fa) continue; dfs(to,x); size[x]+=size[to]; for(int j=n-1;j>=0;j--) if(dp[x][j]) dp[x][j+size[to]]=1; ///枚举x的儿子节点染相同颜色然后标记 } int num=n-size[x]; for(int i=n-1;i>=0;i--){ if(dp[x][i]) dp[x][i+num]=1; ///染相反的颜色 } for(int i=1;i<n;i++) if(dp[x][i]) flag[i]=1; } signed main(){ fio scanf("%d",&n); for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); ans[u].pb(v); ans[v].pb(u); } dfs(1,0); int a=0; for(int i=1;i<n-1;i++) if(flag[i]) a++; cout<<a<<endl; for(int i=1;i<n-1;i++) if(flag[i]) cout<<i<<" "<<n-i-1<<endl; system("pause"); return 0; }