【题意】
给定两棵都是N个节点的有根树A,B,节点均从1..N标号。
我们需要给每个标号定一个权值,使在两棵树上均满足任意节点子树权值和为1或?1
输出任意一种解,需要判断无解 N?100000
【分析】
这是一道很好的构造题目
我们考虑到每个子树的和为1/-1都是奇数,所以我们可以通过每个点的儿子数来判断奇偶性,如果两棵树对应节点奇偶性不同,那么就是不合法的
然后我们就需要构造一组合法的解了
这个的方法就很神奇了,由于涉及了度数的问题,还和奇偶性相关,我们就要想到构造欧拉回路了
构造方式如下:
给度数为奇数的点,两棵树之间对应点连横叉边
把两个数的根节点都连向一个虚拟根节点
这时图上所有的点的度数都是偶数了,一定存在欧拉回路
我们给欧拉回路随便定个方向,这时候的答案就是可行解了,这个具体的就就理解理解把
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define mp make_pair #define fi first #define se second const int maxn=2e5+5; struct edge { int u,v; }e[maxn<<2]; int n,d[maxn],rt1,rt2; vector <int> G[maxn]; int cnt; void add(int u,int v) { cnt++; e[cnt].u=u; e[cnt].v=v; G[u].push_back(cnt); G[v].push_back(cnt); d[u]++; d[v]++; } int vis[maxn<<2],ans[maxn]; void dfs(int u) { while(!G[u].empty()) { int id=G[u].back(); G[u].pop_back(); if(vis[id]) continue; vis[id]=1; int to=e[id].u^e[id].v^u; if(id>2*n) if(u>to) ans[to]=1; else ans[u]=-1; dfs(to); } } int main() { // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); scanf("%d",&n); int x; for(int i=1;i<=n;i++) { scanf("%d",&x); if(x!=-1) add(i,x); else rt1=i,add(n+1,i); } for(int i=1;i<=n;i++) { scanf("%d",&x); if(x!=-1) add(i+1+n,x+1+n); else rt2=i,add((n+1)*2,i+n+1); } for(int i=1;i<=n+1;i++) { if(d[i]%2!=d[n+1+i]%2) { printf("IMPOSSIBLE\n"); return 0; } if(d[i]&1) add(i,i+n+1); } dfs(1); printf("POSSIBLE\n"); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }