题解 AT2675 【Two Trees】

· · 题解

同步发布于我的博客Two Trees

对于每棵树，都满足每个点的子树点权和在\bmod 2意义下是1，所以可以从下往上递推出每个点权的奇偶性。需要满足每个点在两棵树中奇偶性相同，否则无解。

更具体地，当一个点有偶数个儿子时点权\bmod 2 = 1，有奇数个儿子时点权\bmod 2 = 0

有这么一种构造方法，只要令偶数点权 = 0，奇数点权 = +1或-1即可构造出解。具体如下（称点权\bmod 2 = 1的点为奇点）： 选择任意一个奇点为特殊点。对于两棵树，首先从下往上进行匹配 匹配到点u时，每个子树中会多出一个奇点，包括u本身，如果是奇点也算在内，会有2k + 1个奇点。这些点去掉任意一个点之后对于剩下的点，任意两两匹配。如果匹配了x和y，就连一条无向边(x, y)。被去掉的点就是该子树多出来的点

进行了这样的匹配操作后，显然有：

  1. 任意u的子树中有2k + 1个奇点，其中有k对奇点两两匹配，被去掉的点就是在u处匹配时被去掉的点
  2. 特殊点在两棵树中都没有参与匹配，度数 = 0
  3. 非特殊点的奇点在两棵树中都恰好参与一次匹配，度数 = 2

图由若干个环构成，同时一个点连接的两条边是在不同的树中的匹配，所以每个环都是偶环，该图是二分图。令黑点权值 = +1，白点权值 = -1，进行这样的操作后，每一对匹配的点权和是0，每个子树的点权和由该子树中多出来的点决定。显然也就完成了构造。

时间复杂度\mathcal O(n)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n, f[MAXN], dis[MAXN];
template <class T>
inline void _read(T &x)
{
    x = 0;
    char t = getchar();
    while(!isdigit(t) && t != '-') t = getchar();
    if(t == '-')
    {
        _read(x);
        x *= -1;
        return ;
    }
    while(isdigit(t))
    {
        x = x * 10 + t - '0';
        t = getchar();
    }
}
inline int getfa(int x)
{
    if(f[x] == x)
        return x;
    int fx = getfa(f[x]);
    dis[x] ^= dis[f[x]];
    return f[x] = fx;
}
inline void merge(int u, int v)
{
    int x = getfa(u), y = getfa(v);
    if(x == y) return;
    dis[y] = (dis[v] ^ dis[u] ^ 1), f[y] = x;
}
struct T
{
    int root, head[MAXN], cnt, to[MAXN], nxt[MAXN], son[MAXN];
    inline void ae(int u, int v)
    {
        ++cnt, to[cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
    }
    inline void init()
    {
        for(int i = 1, fa; i <= n; ++i)
        {
            _read(fa);
            if(fa == -1)
                root = i;
            else
                ae(fa, i), ++son[fa];
        }
    }
    inline int work(int u)
    {
        vector<int> tp;
        for(int i = head[u]; i; i = nxt[i])
            tp.push_back(work(to[i]));
        if(!(son[u] & 1))
            tp.push_back(u);
        sort(tp.begin(), tp.end());
        for(int i = 1; i < tp.size(); i += 2)
            merge(tp[i], tp[i + 1]);
        return tp[0];
    }
};
T A, B;
int main()
{
    _read(n);
    A.init(), B.init();
    for(int i = 1; i <= n; ++i)
    {
        f[i] = i, dis[i] = 0;
        if((A.son[i] & 1) != (B.son[i] & 1))
        {
            puts("IMPOSSIBLE");
            return 0;
        }
    }
    puts("POSSIBLE");
    A.work(A.root), B.work(B.root);
    for(int i = 1; i <= n; ++i)
        if(!(A.son[i] & 1))
            printf("%d ", (getfa(i), dis[i]) ? +1 : -1);
        else
            printf("%d ", 0);
    return 0;
}