ARC143E Reversi

简单的分析题。

思路

如果分析一个节点状态，那么时不方便的。但可以注意到，状态的改变好相连的边数有关。

从叶子节点开始考虑。

• 白色：在父亲翻转前选中，并改变父亲状态。
• 黑色：在父亲翻转后选中。

这里可以用拓扑排序建边描述这个问题。

我们把叶子节点解决后，在按照一样的方法，逐层向上解决问题。

最后如果根节点变成黑色，那么无解，否则拓扑排序输出答案（可以开小根堆优先队列，先访问小点）。

CODE

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

const int maxn=2e5+5;

struct Edge
{
    int tot;
    int head[maxn];
    struct edgenode{int to,nxt;}edge[maxn*2];
    void add(int x,int y)
    {
        tot++;
        edge[tot].to=y;
        edge[tot].nxt=head[x];
        head[x]=tot;
    }
}E,G;

int n;
int ind[maxn];

bool vis[maxn];

void dfs(int u,int f)
{
    for(int i=E.head[u];i;i=E.edge[i].nxt)
    {
        int v=E.edge[i].to;
        if(v==f) continue;
        dfs(v,u);
    }
    if(u==1&&vis[u]){printf("-1");exit(0);}
    else if(u==1) return ;
    if(vis[u]) G.add(f,u),ind[u]++;
    else G.add(u,f),ind[f]++,vis[f]^=1;
}
int cnt;
int ans[maxn];
priority_queue<int,vector<int>,greater<int>>que;
void topu()
{
    for(int i=1;i<=n;i++) if(ind[i]==0) que.push(i);
    while(!que.empty())
    {
        int u=que.top();
        que.pop();
        ans[++cnt]=u;
        for(int i=G.head[u];i;i=G.edge[i].nxt)
        {
            int v=G.edge[i].to;
            if(!(--ind[v])) que.push(v);
        }
    }
    for(int i=1;i<=cnt;i++) printf("%d ",ans[i]);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        E.add(u,v);
        E.add(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        char op;
        cin>>op;
        vis[i]=(op=='B');
    }
    dfs(1,0);
    topu();
}