Two Trees[AGC018F][欧拉回路][构造]_综合

文章目录

题目
思路
代码

题目

在这里插入图片描述
Luogu

思路

对于一个点的儿子所在子树都是 $+ 1 / ? 1$ 那么猜测当 $u$ 向下度数为奇数 $val_u=0$ 为偶数 $valu=±1val_u=\pm1$
当点在两棵树奇偶性不同时候显然不合法( $u$ 点奇偶性不匹配)
除此之外尝试构造方案
然后向下度数为偶数点相互连接，然后根节点之间再连接
然后跑欧拉回路，根据相同点之间边的决定权值
尝试证明为什么是对的
首先所有点度数为偶数，一定能构造欧拉回路
然后对于一个子树内部路径只有如下情况：
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
发现第三种情况不改变子树内权值和，同时由于通往父亲的边只有一条，那么权值 $=±1=\pm1$ 得到了保证
欧拉路径类似当前弧优化的就不提了

代码

#include<set>
#include<map>
#include<cmath>
#include<deque>
#include<stack>
#include<ctime>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define fi first
#define se second
#define mp make_pair
const int MAXN=500000;
const int INF=0x3f3f3f3f;
int n,rt1,rt2;
bool vis[4*MAXN+5];
int de[2*MAXN+5],tp[2*MAXN+5];
int X[MAXN+5];
vector<pair<int,int> > G[2*MAXN+5];
void DFS(int u){
    for(int &i=tp[u];i<(int)G[u].size();i++){
    int v=G[u][i].first,id=G[u][i].second;if(vis[id]) continue;vis[id]=1;if(u+n==v) X[u]=1;if(u==v+n) X[v]=-1;DFS(v);}return ;
}
int main(){
    n=read();int cnt=0;for(int i=1,a;i<=n;i++){
    a=read();if(a==-1) rt1=i;else G[a].push_back(mp(i,++cnt)),G[i].push_back(mp(a,cnt)),de[i]++,de[a]++;}for(int i=1,b;i<=n;i++){
    b=read();if(b==-1) rt2=i;else G[n+b].push_back(mp(n+i,++cnt)),G[n+i].push_back(mp(n+b,cnt)),de[n+i]++,de[n+b]++;}de[rt1]++,de[n+rt2]++;G[rt1].push_back(mp(2*n+1,++cnt));G[2*n+1].push_back(mp(rt1,cnt));for(int i=1;i<=n;i++){
    if((de[i]^de[i+n])&1)puts("IMPOSSIBLE"),exit(0);if(de[i]&1){
    G[i].push_back(mp(i+n,++cnt));G[i+n].push_back(mp(i,cnt));}}puts("POSSIBLE");DFS(rt1);for(int i=1;i<=n;i++)printf("%d",X[i]),putchar(i==n?'\n':' ');return 0;
}