AT2675

· · 题解

题目：Two Trees

感觉二分图的题解稍微显得比较少，由于最近本蒟蒻在学二分图，就决定来用二分图写一下这道题。

和大家的思路一样，都是对每个节点儿子数量的奇偶性分类讨论进行构造。

本蒟蒻第一眼看到这道题的时候，觉得这道题真的太难了。于是，本蒟蒻决定把它改的简单一点。请看：

那就让我们从最简单的情况开始思考。

对于一个深度为二的树，我们需要做的就是把根的儿子们两两配对，每一对儿子都是一个权值为 1 ，一个为 -1 ；如果最后没有剩下孩子的话，那么就把根节点的权值赋为 1 （或者 -1 随便）；如果还剩一个孩子的话，那么就把根节点的权值赋为 0 。

那么问题来了，如何表示两个节点的“配对”关系呢？

你想啊，有一对节点，一个是 1 ，一个是 -1 ，不就是相当于是两类节点吗。而在两类节点之间存在一个关系，那肯定会想到用二分图。于是就可以小题大做地把“一对”的儿子节点连起来。

解决了这个问题，那就让我们升级难度，如果只有一棵树的话，那应该如何构造一个合法解呢？

考虑每个节点，它必然会有许许多多的儿子，你可以发挥想象力，把以它的每一个儿子为根节点的子树想象成一个大大的节点，而题目中规定了，这个大大的节点总权值一定是 1 或 -1 。

那不就是上面那个问题了吗。 我们也可以同样地，按照节点的儿子数量进行分类讨论，并把“一对”的儿子连起来。

等等，刚才我们可以连起来，是因为它的“儿子”是一个个节点；现在呢，它的“儿子”是一棵棵子树，而树和树是没法连起来的。

怎么办呢？

为了解决这个问题，我们引入“决定点”的概念。

由于我们连边的目的是把一对“ 1 子树”和“ -1 子树”连起来，那么我们考虑是否可以用一个节点的权值来代表一棵子树的权值呢？这样我们就可以通过连接两个“决定点”来连接两棵子树了。

这不就好了吗，接下来的问题就是 如何求出一棵子树的“决定点”。

还是考虑对儿子数进行分类讨论：

然后正常连边就可以了。

解决了这些，两棵树这个问题就简单了，对于两棵树都按照法则加一次边就可以了。

至于为什么形成的图会是二分图？抱歉证明不是本蒟蒻的强项，感性地解释一下就是，同一棵树内，由于一棵子树的“决定点”只会被引用一次，也就是连一次边，所以一个节点的度数一定是 1 ；增加了一棵树了之后，要形成环就只能从另一棵树上的信息连一条边过来，所以不会是奇环，根据二分图的判定，这个图一定会是二分图。我只能扯到这里了……

上代码(AC记录)

#include<cstdio>
#include<cstring>
//#define zczc
using namespace std;
const int N=100010;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar(); }
    wh*=f;return;
}

int m;
bool odd[N],odd2[N];//在两棵树中某个节点的孩子数量是否为奇数 

//graph中是二分图部分 
namespace graph{
    struct edge{
        int t,next;
    }e[N<<1];
    int head[N],esum;
    inline void add(int fr,int to){
        esum++;
        e[esum].t=to;
        e[esum].next=head[fr];
        head[fr]=esum;
        return;
    }
    bool vis[N],black[N];
    //二分图标记颜色 
    void dfs(int wh,bool color){
        vis[wh]=true;
        black[wh]=color;
        for(int i=head[wh],th;i;i=e[i].next){
            th=e[i].t;
            if(vis[th])continue;
            dfs(th,!color);
        }
        return;
    }
}
//tree中是树的部分
//个人感觉分开来写要清晰一些 
namespace tree{
    struct edge{
        int t,next;
    }e[N];
    int head[N],esum;
    inline void add(int fr,int to){
        esum++;
        e[esum].t=to;
        e[esum].next=head[fr];
        head[fr]=esum;
        return;
    }
    int decide[N];//标记每个节点为根的子树的“决定点” 
    bool second;
    void dfs(int wh){
        bool oddnum=false;//动态显示孩子数量的奇偶性 
        int son=0,last=0;//son是落单的孩子，last是方便“配对”孩子用的 
        for(int i=head[wh];i;i=e[i].next){
            oddnum=!oddnum;
            dfs(e[i].t);
            son=e[i].t;
            if(last==0)last=e[i].t;
            else{
                graph::add(decide[last],decide[e[i].t]);
                graph::add(decide[e[i].t],decide[last]);
                last=0;
            }
        }
        if(second)odd2[wh]=oddnum;
        else odd[wh]=oddnum;
        //如果有奇数个孩子就取决于落单的孩子 
        if(oddnum)decide[wh]=decide[son];
        //如果有偶数个孩子就自己决定 
        else decide[wh]=wh;
        return;
    }
    void solve(){
        //输入，没什么好说的 
        read(m);
        int s1,root;
        for(int i=1;i<=m;i++){
            read(s1);
            if(s1==-1)root=i;
            else add(s1,i);
        }
        dfs(root); 
        memset(head,0,sizeof(head));
        esum=0;
        for(int i=1;i<=m;i++){
            read(s1);
            if(s1==-1)root=i;
            else add(s1,i);
        }
        second=true;
        dfs(root);
        for(int i=1;i<=m;i++){
            if(odd[i]!=odd2[i]){
                printf("IMPOSSIBLE\n");
                return;
            }
        }
        printf("POSSIBLE\n");
        for(int i=1;i<=m;i++){
            if(graph::vis[i])continue;
            graph::dfs(i,true);
        }
        for(int i=1;i<=m;i++){
            if(odd[i])printf("0 ");
            else{
                if(graph::black[i])printf("1 ");
                else printf("-1 ");
            }
        }
        return;
    }
}

signed main(){

    #ifdef zczc
    freopen("in.txt","r",stdin);
    #endif

    tree::solve();

    return 0;
}

本蒟蒻写了差不多一个小时，管理员求过，谢谢啦。

注：先前没注意 \LaTeX 的使用，抱歉啦，本蒟蒻下次一定注意。