题目描述：
一棵N(N<5,000)个节点的树，染两种颜色，不同颜色不能相邻且要给尽可能多的节点染色。求颜色A和颜色B可能的染色节点个数。
算法分析：
显然是只有一个节点不染色的时候最优，之前要求出这个节点所有子树的孩子的个数，这个需要树形DP。
然后每个不染色的节点，哪些孩子染哪些颜色，有多少不同的数量，这个是背包。
然后让我纠结的是，为啥大家都把背包当水题做？
#include<iostream>
#include<cstdio>
using namespace std;
const int V = 5005;
const int E = V<<1;
int n,e,head[V],nxt[E],pnt[E];
bool ans[V],dp[V][V];
void add(int u,int v){
nxt[e] = head[u]; head[u]=e;pnt[e] = v;e++;
}
int sum[V];
void dfs(int u,int f){
sum[u] = 1;
dp[u][0] = 1;
for(int i=head[u];i!=-1;i=nxt[i]){
int v = pnt[i];
if(v==f) continue;
dfs(v,u);
sum[u] += sum[v];
for(int i=n-1;i>=0;i--)
if(dp[u][i])
dp[u][i + sum[v]] = 1;
}
int s = n-sum[u];
for(int i=n-1;i>=0;i--)
if(dp[u][i]) dp[u][i+s] = 1;
// cout<<"u: "<<u<<endl;
// for(int i=0;i<n;i++) if(dp[u][i]) cout<<i<<" "; cout<<endl;
for(int i=0;i<n;i++)
ans[i] |= dp[u][i];
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) head[i] = -1;
int u,v;
e = 0;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
u--; v--;
add(u,v);
add(v,u);
}
dfs(0,0);
int len = 0;
for(int i=1;i<n-1;i++)
len += ans[i];
printf("%d\n",len);
for(int i=1;i<n-1;i++) if(ans[i]){
printf("%d %d\n",i,n-1-i);
}
return 0;
}
posted on 2012-07-21 22:47
西月弦 阅读(285)
评论(0) 编辑 收藏 引用 所属分类:
解题报告