AT2675 [AGC018F] Two Trees

【题意】

给定两棵都是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;
}

 

 

 

AT2675 [AGC018F] Two Trees

上一篇:vue、vue-antd 动态表格,table某一列两个input


下一篇:九度OJ 1118 数制转换