AT2675 [AGC018F] Two Trees

解题报告

AT2675 [AGC018F] Two Trees解题报告：

更好的阅读体验

题意

• 给定两颗树，你需要给位置$x$一个值$v_x$，使得$x$在两棵树上的子树和的绝对值均为$1$；
• 如果没有方案，输出$\text{IMPOSSIBLE}$，否则输出$\text{POSSIBLE}$，并给出方案。
• 数据范围：$1\leqslant n\leqslant 10^5$。

分析

欧拉回路神仙题。

注：以下称第一棵树为左树，第二棵树为右树。

我们先考虑判断无解：因为每个子树的权值和为$1/-1$，而它们都是奇数，因此我们需要判断一个相同的点在左树和右树中儿子数量的奇偶性是否相同，如果不同，那么无解。

由于牵扯到了儿子个数的奇偶性，可以转化为度数的奇偶性（如果要用度数的奇偶性判断别忘了把根的度数加一），如果你见过的题比较多，应该可以迅速想到构造一个图在上面跑欧拉回路。

具体地，我们对于度数为偶数的点不管它们，对于度数为奇数的点，我们将它们对应左树和右树的两个点连边（下文称作横叉边），同样把两个根结点连一条边。我们发现这个图里所有点的度数都是偶数，即它存在欧拉回路。

我们跑一遍欧拉回路，对于度数为偶数的点，我们设定它的权值为$0$，对于度数为奇数的点，如果它对应的横叉边在欧拉回路上的方向是从左往右，那么我们设定它的权值为$1$，否则为$-1$。

考虑证明这种构造方法的正确性：

我们把欧拉回路拆成若干个简单环，对于一个环对某个结点的贡献，我们分三类情况讨论：

• 某个节点往儿子走，然后从儿子或自己的横叉边回来；
• 某个节点往儿子走，然后从父亲回来；
• 某个节点往横叉边/父亲走，然后从父亲/横叉边回来。

对于第一类环，我们发现从一颗树到另一颗树会贡献一次$1$也贡献一次$-1$，且这两次贡献都在这个结点中，所以这个环对这个结点无贡献。

对于第二类环和第三类环，我们发现这个环只会对该结点造成$1/-1$的贡献。

考虑第二类环和第三类环都要经过父亲，而父亲到该节点的边只能也必须经过一次，因此第二类环和第三类环有且仅有一个。

对于两棵树的根：我们将两个根连边其实等价于建立一个虚拟根，成为左树和右树根的父亲。这样，对于原树的根，我们也可以看成上述情况，对于虚拟根则不需要进行讨论（它的权值对答案没有影响）。

这样，我们每颗子树的权值和的绝对值便是$1$了。

代码

注意欧拉回路需要用当前弧优化（其实就是在$\text{vector}$里$\text{pop_back}$）

#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=800005,maxm=800005;
int n,rt1,rt2,cnt,flg;
int deg1[maxn],deg2[maxn],used[maxn],ans[maxn],f[maxm],xx[maxm],yy[maxm];
vector<int>v[maxn];
inline void add(int x,int y,int fl){
    cnt++,v[x].push_back(cnt),v[y].push_back(cnt),xx[cnt]=x,yy[cnt]=y,f[cnt]=fl;
}
void dfs(int x){
    while(!v[x].empty()){
        int i=v[x].back();
        v[x].pop_back();
        if(used[i]==0){
            int y=xx[i]^yy[i]^x;
            used[i]=1;
            if(f[i]==1)
                ans[min(x,y)]=x<y? 1:-1;
            dfs(y);
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        if(x==-1)
            rt1=i;
        else add(i,x,0),deg1[i]++,deg1[x]++;
    }
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        if(x==-1)
            rt2=i;
        else add(n+i,n+x,0),deg2[i]++,deg2[x]++;
    }
    deg1[rt1]++,deg2[rt2]++,add(rt1,n+rt2,0);
    for(int i=1;i<=n;i++)
        if(deg1[i]%2!=deg2[i]%2){
            flg=1;
            break;
        }
    if(flg){
        puts("IMPOSSIBLE");
        return 0;
    }
    for(int i=1;i<=n;i++)
        if(deg1[i]%2)
            add(i,n+i,1);
    dfs(1);
    puts("POSSIBLE");
    for(int i=1;i<=n;i++)
        printf("%d%c",ans[i],i==n? '\n':' ');
    return 0;
}