题解：【PA2021】 Drzewo czerwono-czarne

· · 题解

神秘的阅读体验

题目链接

首先有三种情况是平凡的：

  1. 起始和终止相同，显然有解
  2. 起始中只有一种颜色并且终止和起始并不相同，显然无解
  3. 考虑最后一步，一定是将某一条边上的一个点改成另一个点的颜色，所以终止的颜色序列中必定有一条边上的两个点颜色相同，即必有 (x,y) \in G 且 col_x=col_y，否则无解。

增大限制，如果放在链上这个东西怎么判断。链上的颜色一定形如 \text{BRBRBR} 或者 \text{RBRBRB}。所以如果起始的连续颜色段数不少于终止的连续颜色段数，注意到终止状态中的一个颜色段至少可以对应上起始状态中的一个颜色段，那么就可以不断挪动来得到解。特别的，如果在链的开头起始和终止颜色不同，那么起始就要少算一个连续段，原因是我们的颜色段只能伸展，不能交换顺序或者分裂开在中间插入新的颜色。

做完了链剩下的一定是一棵多叉树。

显然，样例中的情况是先用 2 把 3,4 染红，然后用 1 把 2 染白。

也不难发现，对于四个点来说，只要有一个点度数为 3 就必定有解，证明如下：

  1. 设有这么一个四点三边的结构 (x,a)，(x,b)，(x,c)，其中 col_x=0 我们要使得终止状态为 col_a=0,col_b=col_c=1
  2. 如果初始终止状态相同，自然有解
  3. 如果 col_a=col_b=col_c=1，操作 x \to a 即可
  4. 如果 col_a=col_b=0,col_c=1，操作 c \to x，x \to b，a \to x 即可
  5. 如果 col_a=col_b=col_c=0，因为我们保证了要先满足树上必定有两种颜色，否则一定无解，所以先随便在外头找一个 col_i=1 的点 i，然后一路染过来使得 col_x=1，如果这期间使得状态变成了 col_x=col_a=1，那么操作 x \to b，c \to x，x \to a，b \to x x \to c a \to x。如果 col_a=0 那么就先把 col_x 变成 1，染完 b,c 后再用 a 把 x 染回来
  6. 对于 col_x=1 也是一样的分讨操作

从上面我们可以知道只要我们最后能把树转化成上面的结构，那么通过调整颜色就一定能够得到解。大胆猜想，只要树中有点度数为 3 就必定有解，证明如下：

  1. 从三叉树开始考虑，不妨将度数为 3 的 x 记为根。我们首先处理 a 下面的链。在 b 节点上存一个红，在 c 节点上存一个黑，那么此时 x 就可以看作一个可以变色的链头，用类似于处理链的方式将 a 的链染合法。
  2. 此时再将 a 作为储存点，用相同的道理继续处理 b 的链和 c 的链。
  3. 可以发现当每条链都合法后，我们成功转化出了上面的结构，剩下的就是四个点之间的转化，这个是好做的。
  4. 对于多叉的推广情况是相同的。

于是这道题就做完了，我们只需要判断是否符合上面几个情况。时间复杂度为 O(n)，瓶颈在于找链的连续颜色段数量的遍历，注意判断答案的顺序。

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read()
{
    int s=0,w=1;
    char c=getchar();
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
    return s*w;
}
inline void READ(char *s)
{
    int num=0;
    char c=getchar();
    while(c!='0'&&c!='1') c=getchar();
    while(c=='0'||c=='1') s[++num]=c,c=getchar();
    return;
}

namespace LgxTpre
{
    static const int MAX=200010;
    static const int INF=4557430888798830399;
    static const int mod=998244353;

    int T,n;
    int x,y;
    char s1[MAX],s2[MAX];

    struct edge
    {
        int nex,to;
    }e[MAX<<1];
    int head[MAX],cnt;
    inline void add(int x,int y)
    {
        e[++cnt].nex=head[x];
        head[x]=cnt;
        e[cnt].to=y;
        return;
    }

    int deg[MAX];
    int num1,num2;
    void dfs(int now,int father)
    {
        if(s1[now]!=s1[father]) ++num1;
        if(s2[now]!=s2[father]) ++num2;
        for(int i=head[now];i;i=e[i].nex)
        {
            int to=e[i].to;
            if(to!=father) dfs(to,now);
        }
        return;
    }
    inline void init()
    {
        for(int i=1;i<=n;++i)
            head[i]=deg[i]=0;
        cnt=num1=num2=1;
        return;
    }

    inline void lmy_forever()
    {
        T=read(); 
        while(T--)
        {
            init();
            n=read(),READ(s1),READ(s2);
            int flag1=1,flag2=0,flag3=1,flag4=1,s;
            for(int i=1;i<n;++i)
            {
                x=read(),y=read(),
                ++deg[x],++deg[y],
                add(x,y),add(y,x);
                if(s2[x]==s2[y]) flag3=0;
            }
            for(int i=1;i<=n;++i)
            {
                if(s1[i]!=s1[i-1]&&i!=1) flag1=0;
                if(deg[i]>=3) flag2=1;
                if(s1[i]!=s2[i]) flag4=0;
                if(deg[i]==1) s=i;
            }
            if(flag4)        {printf("TAK\n"); continue;}
            if(flag1||flag3) {printf("NIE\n"); continue;}
            if(flag2) {printf("TAK\n"); continue;}
            dfs(s,s);
            if(s1[s]!=s2[s]) --num1;
            if(num1<num2) printf("NIE\n");
            else printf("TAK\n");
        }
        return;
    }
}

signed main()
{
    LgxTpre::lmy_forever();
    return (0-0);   
}