描述

给定一棵树，对每个节点用两种颜色染色，要求每个点周围只有一个点和其同色，如果可以输出方案，如果不可以输出-1

思路

• 写的好拉啊？但是没想到很优雅的写法啊？
• 本质上是个匹配的问题，即树上每个点只能匹配一个点，问可不可以每个点都有匹配，设树的根为$11$，$dp[i][0]dp[i][0]$可不可以表示节点$ii$和子树当中的某个点匹配，$dp[i][1]dp[i][1]$表示节点$ii$可以不可以和父亲进行匹配，则转移方程为

• 当$dp[1][0]=falsedp[1][0]=false$或者某个非根节点$vv$,$dp[v][0]=dp[v][1]=falsedp[v][0]=dp[v][1]=false$时,输出$-1-1$,否则根据匹配结果生成答案即可

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
vector<int> E[MAXN];
bool dp[MAXN][2];
int pre[MAXN],co[MAXN];
void dfs1(int now,int fa)
{
    for(int v:E[now])
    {
        if(v==fa)
            continue;
        dfs1(v,now);
    }
    int one=-1;
    bool f=true;
    for(int v:E[now])
    {
        if(v==fa)
            continue;
        if(!dp[v][0])
        {
            one=v;
            f=false;
            break;
        }
    }
    if(one==-1&&f)
        for(int v:E[now])
        {
            if(v==fa)
                continue;
            if(dp[v][1])
            {
                one=v;
                break;
            }
        }
    bool flag=true;
    for(int v:E[now])
    {
        if(v==one||v==fa)
            continue;
        if(!dp[v][0])
            flag=false;
    }
    if(one!=-1&&flag)
    {
        dp[now][0]=true;
        pre[now]=one;
    }
    dp[now][1]=true;
    for(int v:E[now])
        if((!dp[v][0])&&v!=fa)
            dp[now][1]=false;
}
void dfs2(int now,int fa,int st)
{
    if(st==1)
    {
        for(int v:E[now])
        {
            if(v==fa)
                continue;
            co[v]=co[now]^1;
            dfs2(v,now,0);
        }
    }
    else
    {
        if(pre[now]==0)
            return ;
        co[pre[now]]=co[now];
        dfs2(pre[now],now,1);
        for(int v:E[now])
        {
            if(v==fa||v==pre[now])
                continue;
            co[v]=co[now]^1;
            dfs2(v,now,0);
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs1(1,0);
    for(int i=1;i<=n;i++)
        if(!dp[i][0]&&!dp[i][1])
            return 0*puts("-1");
    if(!dp[1][0])
        return 0*puts("-1");
    dfs2(1,0,0);
    for(int i=1;i<=n;i++)
        printf("%c",co[i]?'R':'B');
    puts("");
}

时间复杂度$O(n)O(n)$，空间复杂度$O(n)O(n)$