DP58 红和蓝
不会，看的其他博客，感觉解释的挺好的：http://t.csdn.cn/89SbY
描述
你拿到了一棵树，请你给每个顶点染成红色或蓝色。
要求：每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点。
“周围”的定义：某点周围的点指通过邻边直接连接的点。
所谓树，即没有自环、重边和回路的无向连通图。
输入描述：
第一行一个正整数 nn，代表树的顶点个数.。
接下来的 n-1n−1 行，每行两个正整数 uu 和 vv，代表点 uu 和点 vv 有一条边连接。 (1 \leq u,v \leq n)(1≤u,v≤n)
保证输入的一定是一棵合法的树。
输出描述：
如果可以达成染色的要求，请输出一个长度为 nn 的字符串，第 ii 个字符代表第 ii 个顶点的染色情况，'B' 代表蓝色，'R' 代表红色。（若有多种合法染色的方法，输出任意一种即可）
否则直接输出-1。
示例1
输入：
4 1 2 2 3 3 4
复制输出：
RRBB
复制说明：
1为红点，它连接的边有只有一个红点：2
2为红点，它连接的边有只有一个红点：1
3为蓝点，它连接的边有只有一个蓝点：4
4为蓝点，它连接的边有只有一个蓝点：3
示例2
输入：
4 1 2 1 3 1 4
复制输出：
-1
复制说明：
可以证明，无论怎么染色，都无法满足题目的要求。
#include <iostream>
#include<string.h>
using namespace std;
int dp[100005];
int idx=0;
int print_color[100005];
//给每条边一个index,，也就是pos
struct edge{
int value;
int next;
}edge[200015];
int head[100005];// 存储树的索引节点
void addedge(int x,int y,int pos)
{
edge[pos].value=y;
edge[pos].next=head[x];
head[x]=pos;
}
int dfs1(int x,int fa)
{
int sub_node=0;
for(int i=head[x];i!=-1;i=edge[i].next)
{
if(edge[i].value==fa)
{
continue;
}
sub_node++;
if(dfs1(edge[i].value,x)) return 1;
}
if(sub_node==0 ||dp[x]==0) //判断x是叶子节点的条件
{
if(dp[fa]!=0) return 1;
//判断x是不是叶子节点，如果是的话，x的父节点（fa）也没没标记过，说明x是fa唯一的叶节点
dp[x]=++idx;
dp[fa]=idx;
}
return 0;
}
void dfs2(int x,int fa)
{
for(int i=head[x];i!=-1;i=edge[i].next)
{
if(edge[i].value==fa)
{
continue;
}
if(dp[x]==dp[edge[i].value])
{
print_color[edge[i].value]=print_color[x];
}
else{
print_color[edge[i].value]=!print_color[x];
}
dfs2(edge[i].value,x);
}
}
int main() {
int n,pos=1;
scanf("%d",&n);
memset(head,-1,sizeof(head));
memset(edge,-1,sizeof(edge));
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
addedge(a,b,pos);
pos++;
addedge(b,a,pos);
pos++;
}
int res1=dfs1(1,0);
if(res1||dp[0])
{
printf("-1\n");
return 0;
}
print_color[1]=1;
dfs2(1,0);
for(int i=1;i<=n;i++)
{
if(print_color[i]==1)
{
printf("R");
}
else{
printf("B");
}
}
printf("\n");
return 0;
}