传送门

首先我们可以直接根据每个点的儿子个数来确定这个点权值的奇偶性。如果某个点在两棵树里的奇偶性不一样,则显然无解。否则,我们可以通过以下方法构造出一组解,使得权值为偶数的点全部取$0$,剩下的点要么是$1$要么是$-1$。

对于每棵树,我们可以把所有奇数的点两两配对(由于奇数点的数量是奇数,所以会剩下一个点不参与配对),使得对于每棵子树,设子树中的奇数点有$2k+1$个,我们都可以在子树中找出$k$对配对的奇数点(还有一个点没有在子树内部配对)。则我们可以钦定每对点一个取$1$,一个取$-1$,这样每个子树的权值和的绝对值就是$1$了。

我们把两棵树的配对情况都拿出来连边,这样建出来的图显然是不含奇环的,所以是个二分图。我们直接把二分图左边的点赋成$1$,右边的点赋成$-1$,就能满足条件了。

#include <cstdio>
#include <cstring>
#define MAXN 1000010

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN];

int n,root;
int g[MAXN],nume;
int e2[MAXN][2],nume2;
int d[MAXN],d0[MAXN];
int c[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

int dfs(int x){
    int cnt=0;
    int last=0;
    for(int i=g[x];~i;i=e[i].next){
        cnt^=1;
        int temp=dfs(e[i].to);
        nume2++;
        if(last){
            e2[nume2][0]=last;
            e2[nume2][1]=temp;
            last=0;
        }else last=temp;
    }
    if(!last) last=x;
    d[x]^=cnt;
    d0[x]=cnt;
    return last;
}

void dfs2(int x){
    for(int i=g[x];~i;i=e[i].next)
        if(!c[e[i].to]){
            c[e[i].to]=-c[x];
            dfs2(e[i].to);
        }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d",&n);
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        if(t!=-1) addEdge(t,i);
        else root=i;
    }
    dfs(root);
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        if(t!=-1) addEdge(t,i);
        else root=i;
    }
    dfs(root);
    for(int i=1;i<=n;i++)
        if(d[i]){
            puts("IMPOSSIBLE");
            return 0;
        }
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=nume2;i++)
        addEdge(e2[i][0],e2[i][1]),addEdge(e2[i][1],e2[i][0]);
    for(int i=1;i<=n;i++)
        if(!d0[i] && !c[i]){
            c[i]=1;
            dfs2(i);
        }
    puts("POSSIBLE");
    for(int i=1;i<=n;i++)
        if(d0[i]) printf("0 ");
        else printf("%d ",c[i]);
}