题解 CF1781G

· · 题解

前言

虚高 3200，很适合作为年轻人的第一个 3000+。

小晚在枝江给大家拜年了！祝大家新年快乐！万事顺利！

题解

考虑如果这棵树上存在完美匹配，那么答案一定是 0，因为将每个匹配中的两个点染上不同的颜色即可。

尝试一种类似的匹配方法：我们 dfs 到每个点时，先 dfs 它的两个儿子，再将没匹配到的点和它放入一组。

假设在上述过程中，根节点被匹配，不难发现每个连通块的大小都是 2 或 3。将大小为 2 的连通块染色不影响答案，而将大小为 3 的连通块染色会让答案 +1 或者 -1。我们依次执行两种操作，不难发现最终答案即为最优答案 n\bmod 2。

接下来考虑根节点不匹配的情况，如果我们直接把这个点强行塞入一个连通块，可能存在一个连通块为 4 个点的菊花图，我们进行一些分类讨论：

三种分类讨论的图示如下：

不难发现同时不在三种情况里的树只有一棵，它已经在样例中出现，特判即可。

时间复杂度 O(n)。

代码

//不回家了，我们去鸟巢！
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int fa[1000003],deg[1000003];
int ls[1000003],rs[1000003];
bool flg[1000003],ans[1000003];
signed main()
{
    for(int T=read();T--;)
    {
        int n=read();
        for(int i=1; i<=n; ++i)
            deg[i]=ls[i]=rs[i]=0,flg[i]=ans[i]=0;
        for(int i=2; i<=n; ++i)
        {
            fa[i]=read();
            if(ls[fa[i]]) rs[fa[i]]=i;
            else ls[fa[i]]=i;
        }
        for(int i=2; i<=n; ++i)
            if(i==4) printf("%d\n",(fa[3]==fa[4])<<1);
            else printf("%d\n",i&1);
        if(n==4&&fa[3]==fa[4])
        {
            puts("wbww");
            continue;
        }
        for(int i=n; i>1; --i)
            if(!flg[i])
                ++deg[fa[i]],flg[fa[i]]=1;
        if(!flg[1])
        {
            if(deg[2]==2&&rs[1]&&deg[rs[1]]==1)
            {
                deg[1]=deg[rs[1]]+1,
                deg[rs[1]]=0,flg[rs[1]]=0,
                flg[1]=1,ans[1]=1;
            }
            else
            {
                deg[1]=deg[2]+1,deg[2]=0,
                flg[2]=0,flg[1]=1,ans[1]=1;
                if(deg[1]==3&&!rs[1])
                {

                    int ok=0;
                    for(int i=2; i<=n; ++i)
                        if(deg[i]==2) ok=1;
                    if(!ok)
                    {
                        int x=0,y=0;
                        if(ls[ls[2]]) x=ls[2],y=ls[ls[2]];
                        if(rs[ls[2]]) x=ls[2],y=rs[ls[2]];
                        if(ls[rs[2]]) x=rs[2],y=ls[rs[2]];
                        if(rs[rs[2]]) x=rs[2],y=rs[rs[2]];
                        --deg[1],flg[x]=1,flg[y]=0,ans[x]=1,
                        deg[x]=deg[y]+1,deg[y]=0;
                    }
                }
            }
        }
        vector<pair<int,int>> vec;
        for(int i=1; i<=n; ++i)
            if(deg[i]>1)
                vec.emplace_back(deg[i]-1,i);
        sort(vec.begin(),vec.end());
        reverse(vec.begin(),vec.end());
        int sum=0;
        for(auto [x,y]:vec)
            if(sum>0) sum-=x,ans[y]^=1;
            else sum+=x;
        assert(sum==(n&1));
        for(int i=2; i<=n; ++i)
            if(!flg[i]) ans[i]=ans[fa[i]]^1;
        int S=0;
        for(int i=1; i<=n; ++i) S+=ans[i];
        for(int i=1; i<=n; ++i)
            putchar(ans[i]?'w':'b');
        int real=abs(S*2-n);
        assert(real==sum);
        puts("");
    }
    return 0;
}