题目大概说有一棵树要给结点染色0或1，要求所有度为1的结点一半是0一半是1，然后问怎么染色，使两端点颜色不一样的边最少。
- dp[0/1][u][x]表示以u结点为根的子树中u结点是0/1色 且其子树有x个结点染成1色 的最少边数
转移就是树上背包了。有点就是各个子树必须选，这种形式的树上背包之前做过，我的做法是用了tmp数组来更新最后再写入根的状态数组中，另外我特判了第一个子树的转移方式。。写得好像有点挫。。
另外根随便选一个度不为1的即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 5500 struct Edge{
int v,next;
}edge[MAXN<<];
int NE,head[MAXN];
void addEdge(int u,int v){
edge[NE].v=v; edge[NE].next=head[u];
head[u]=NE++;
} int leafcnt[MAXN];
void getlc(int u,int fa){
bool isleaf=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
getlc(v,u);
leafcnt[u]+=leafcnt[v];
isleaf=;
}
if(isleaf) leafcnt[u]=;
} int d[][MAXN][MAXN];
void dfs(int u,int fa){
bool isfirst=,isleaf=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
isleaf=;
dfs(v,u);
if(isfirst){
isfirst=;
for(int j=; j<=leafcnt[u]; ++j){
d[][u][j]=min(d[][v][j],d[][v][j]+);
d[][u][j]=min(d[][v][j],d[][v][j]+);
}
}else{
int tmp[][MAXN];
for(int j=; j<=leafcnt[u]; ++j){
tmp[][j]=tmp[][j]=;
}
for(int j=leafcnt[u]; j>=; --j){
for(int k=; k<=min(leafcnt[v],j); ++k){
tmp[][j]=min(tmp[][j],d[][u][j-k]+d[][v][k]+);
tmp[][j]=min(tmp[][j],d[][u][j-k]+d[][v][k]);
tmp[][j]=min(tmp[][j],d[][u][j-k]+d[][v][k]);
tmp[][j]=min(tmp[][j],d[][u][j-k]+d[][v][k]+);
}
}
for(int j=; j<=leafcnt[u]; ++j){
d[][u][j]=tmp[][j];
d[][u][j]=tmp[][j];
}
}
}
if(isleaf){
d[][u][]=;
d[][u][]=;
}
} int deg[MAXN];
int main(){
int n;
scanf("%d",&n);
memset(head,-,sizeof(head));
int a,b;
for(int i=; i<n; ++i){
scanf("%d%d",&a,&b);
addEdge(a,b);
addEdge(b,a);
++deg[a]; ++deg[b];
}
int root;
for(int i=; i<=n; ++i){
if(deg[i]!=){
root=i;
break;
}
}
getlc(root,root);
for(int i=; i<=n; ++i){
for(int j=; j<=n; ++j){
d[][i][j]=d[][i][j]=;
}
}
dfs(root,root);
printf("%d",min(d[][root][leafcnt[root]/],d[][root][leafcnt[root]/]));
return ;
}