【AtCoder Grand Contest 018 F】Two Trees | Mrsrz's blog

构造，二分图黑白染色。

题目大意：

给定两棵 $n$ 个结点的有根树，编号相同的结点的权值相等。

要求确定每个编号的点权，使得两棵树的每棵子树的点权之和都是 $1$ 或 $-1$。

题解：

首先可以得出一个点的点权的奇偶性。如果两棵树得到的奇偶性不一样，则无解。

然后我们考虑只用 $\{1,0,-1\}$ 三个点权解决问题。

对于一个结点连出的每个儿子的子树，我们记录子树中的一个结点的编号，这个结点满足点权为奇数，且它的取值和这整棵树的点权和相等，且子树中其他点都已经“配对”。

我们考虑将所有儿子子树记录的结点两两配对。新建一张 $n$ 个结点的图，然后两个结点之间配对，就表示两个结点正负性不同（我们其实是想让 $1$ 和 $-1$ 消为 $0$）。

若当前这个点有奇数个儿子，则肯定会剩下一个结点没法配对，那么这个点的取值直接影响这棵子树，向上传递编号即可。否则肯定没有剩余的结点，那么当前子树的和就由当前的根的取值决定，向上传递即可。

对两棵树都进行遍历，并建出一张图。由于对一棵树进行遍历时，每个点都只连了一条边，所以最后的图一定是二分图（如果存在奇环，则至少一个结点在同一棵树中连出了两条边，矛盾）。

对二分图黑白染色，表示正负性即可。

Code：

#include<cstdio>
#include<vector>
const int N=1e5+6;int rt1,n,rt2,a[N];std::vector<int>G[N];
void addedge(int u,int v){G[u].push_back(v),G[v].push_back(u);}
struct Tr{
    std::vector<int>G[N];bool p[N];
    int dfs(int now,int pre=0){
        p[now]=1;int pr=0;
        for(int to:G[now])if(to!=pre){p[now]^=1;int x=dfs(to,now);if(pr)addedge(pr,x),pr=0;else pr=x;}
        return pr?pr:now;
    }
}_0,_1;
void dfs(int u,int c){a[u]=c;for(int to:G[u])if(!a[to])dfs(to,-c);}
int main(){
    scanf("%d",&n);
    for(int i=1,x;i<=n;++i){scanf("%d",&x);if(x==-1)rt1=i;else _0.G[x].push_back(i),_0.G[i].push_back(x);}
    for(int i=1,x;i<=n;++i){scanf("%d",&x);if(x==-1)rt2=i;else _1.G[x].push_back(i),_1.G[i].push_back(x);}
    _0.dfs(rt1),_1.dfs(rt2);
    for(int i=1;i<=n;++i)if(_0.p[i]!=_1.p[i]){puts("IMPOSSIBLE");return 0;}puts("POSSIBLE");
    for(int i=1;i<=n;++i){if(_0.p[i]&&!a[i])dfs(i,1);printf("%d ",a[i]);}
    return 0;
}