题解：CF1110G Tree-Tac-Toe

· · 题解

不难发现，黑方不可能胜利。由于只染色三个连点就胜利，而白方不仅先手还提前有白点，因此白方每染色一步，黑方都需要尽可能牵制白方，导致自己不可能获胜。

先从简单的情况入手，考虑初始没有白点的情况。难以发现，有以下四种情况（此外，每一种情况都不能满足前面的情况）。

:::info[情况一]{open}

存在一个点的度数大于 3。称这个点为 A，其邻点中的四个分别为 A_1,A_2,A_3,A_4，如图：

白方染色 A，黑方只能染色一个邻点，不妨染色 A_1，白方染色另一个邻点，不妨染色 A_2，此时未染色的邻点中，至少还有 A_3,A_4。无论黑方染色哪一个，白方都可以染色另一个，因此白方必胜。

:::

:::info[情况二]{open}

存在一个点度数为 3，且连向至少两条没有公共点的、长度至少为 2 的链。称这个点为 A，这两条链分别为 a 链和 b 链，两条链与 A 相连的 A 的邻点分别为 A_1,A_2，剩下的 A 的邻点为 A_3，如图：

白方染色 A，黑方只能染色 A_1,A_2 中的一个，不妨染色 A_1，白方染色 A_2，由于 b 链除了 A_2 外，至少还有一个点 A_4，它一定与 A_2 相连，而 A_3 也与 A 相连。无论黑方染色 A_3,A_4 中的哪一个，白方都可以染色另一个，因此白方必胜。

:::

:::info[情况三]{open}

对于任意一个度数为 3 的点，连向最多一条长度至少为 2 的链。不难发现，最多只存在两个度数为 3 的点，因为如果要加入第三个度数为 3 的点，无论加入到前两个点之间，还是以外，都会进入情况二。情况三要求有且仅有两个度数为 3 的点，称这两个度数为 3 的点为 A,B，其中间必然有一条链使其相连，称这条链为 a=\lbrace a_1,a_2,\dots,a_{m}\rbrace，如图：

白方染色 a_1 或 a_m，不妨染色 a_1，黑方染色 A，白方染色 a_3，黑方染色 a_2……最终会分成两种情况：

:::

:::info[情况四]{open}

不存在或有且仅有一个度数为 3 的点。要么构成一条链，平局；要么白方染色度数为 3 的点，平局。因此平局。

:::

现在考虑初始的白点。如果影响到了以上四种情况，那不坏菜了？所以应尽可能地让初始的白点不影响以上四种情况。

对于初始白点 A，我们考虑添加三个点 A_1,A_2,A_3，使其构成如图形状：

那么，初始白点可以视为是初始无色，白方染色 A，黑方只能染色 A_1，然后 A_2,A_3 都不会被染色了，也就变得无用了。但是，由于不存在 A_1,A_2,A_3，因此黑方等于没有染色，也就是让白方多下了一步，这对以上四种情况不会有影响。（好精妙的做法）

注意，由于每次添加 3 个点，最多会添加 3n 个点，因此最多会有 4n 个点，注意数组大小要开成 2\times 10^6。

四种情况的时间复杂度都是 O\left(n\right) 的，故总时间复杂度为 O\left(\sum n\right)。

const int N=2000005;
int n,m,du[N];
int tot,ver[N<<1],nxt[N<<1],head[N];
inline void add(int x,int y){ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
inline void add_edge(int x,int y){du[x]++,du[y]++,add(x,y),add(y,x);}
char s[N];
inline bool check1()
{
    for(int i=1;i<=n;i++) if(du[i]>3) return true;
    return false;
}
inline bool check2()
{
    for(int x=1;x<=n;x++)
    {
        if(du[x]==3)
        {
            int cnt=0;
            for(int i=head[x];i;i=nxt[i]) if(du[ver[i]]>1) cnt++;
            if(cnt>1) return true;
        }
    }
    return false;
}
int dis[N];
void dfs(int x,int fa)
{
    dis[x]=dis[fa]+1;
    for(int i=head[x];i;i=nxt[i]) if(ver[i]!=fa) dfs(ver[i],x);
}
inline bool check3()
{
    int a=0,b=0;
    for(int i=1;i<=n;i++)
        if(du[i]==3)
        {
            if(!a) a=i;
            else b=i;
        }
    if(!b) return false;
    for(int i=1;i<=n;i++) dis[i]=0;
    dfs(a,0);
    if(dis[b]&1) return true;
    else return false;
}
inline void solve()
{
    n=m=read(),tot=0;
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add_edge(x,y);
    }
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
        if(s[i]=='W')
        {
            add_edge(i,m+1);
            add_edge(m+1,m+2);
            add_edge(m+1,m+3);
            m+=3;
        }
    n=m;
    if(check1()||check2()||check3()) puts("White");
    else puts("Draw");
    for(int i=1;i<=n;i++) du[i]=head[i]=0;
}
int main()
{
    for(int T=read();T;T--) solve();
    return 0;
}

话说为什么洛谷题解在无序列表后面加了图片后，不能继续保持原本的 Tab 啊，只能用折叠框了，跪求管理员大大通过。