2021牛客寒假集训营第一场 C 红和蓝

题意

给一棵树，把他染成红蓝两种颜色。
要求：每个点周围有且仅有有一个点和自己颜色相同
不存在输出-1

分析

首先如果n是奇数肯定不存在，接着考虑其他情况，先说jie'l。
如果存在某一个点，他的 子树的节点数为奇数，这样的子树个数大于1个的话，则无解。

先从叶子节点考虑，因为叶节点只与父节点相连，所以父节点的颜色一定和自己相同。
如果有多个叶子的话，父节点与这些叶节点颜色相同，则无解。
可以推广到，如果子树节点个数为奇数，则必然会多出一个点只能和根组合，若这样的子树个数大于1，无解。

这里证明的并不严谨，只是帮助想象，有兴趣可以自己画一画推一推。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

#define x first
#define y second

const int N = 200010;

int n;
int e[N], ne[N], h[N], idx;
int cnt[N], sz[N]; // 子树的点数奇数的数量，以i为根的点数

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int u, int fa)
{
    sz[u] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        if(!dfs(j, u)) return false;
        sz[u] += sz[j];
        if(sz[j] & 1) cnt[u] ++;
    }
    if(cnt[u] > 1) return false;
    return true;
}

int ans[N];
void dfs2(int u, int fa, int c)
{
    ans[u] = c;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;

        if(sz[j] & 1) dfs2(j, u, c);
        else dfs2(j, u, !c);
    }
}

void solve()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 0; i < n - 1; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    if(n & 1)
    {
        cout << -1 << endl;
        return;
    }
    if(!dfs(1, -1))
    {
        cout << -1 << endl;
        return;
    }
    dfs2(1, -1, 0);
    for(int i = 1; i <= n; i ++)
        if(ans[i]) cout << 'B';
        else cout << 'R';
    cout << endl;
}

int main()
{
    /*ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t --)*/
        solve();
}