题意

有两个有根树 每个树的点都用 $1 \ldots n$ 编号。现在你要给每一个点指定一个权值 满足所有子树的和的绝对值是 1(两棵树上相同编号的点的权值相同)
$n \leq 10^5$

题解

首先我们考虑转化一下题意:由于只有两种状态,考虑给边定向。如果这个子树=1我们就把这个点到父亲的点往下连 否则往上连(上,下都是表示深度)。
发现根没有被考虑到 新建一个虚点 向两个根连边。
我们记这个点的所有儿子的子树和为 $\text{sum}_y$ 这个点的值为 $a_x$ ,这个子树的和为 $\text{sum}_x$。发现我们要满足 $\text{sum}_y-\text{sum}_x+a_x=0$。而且我们发现 $sum_y,sum_x$ 是和出度和入度有关的量。式子可以简化为 $out_x-in_x+a_x=0$。
接下来我们就是要处理形如两个点值相同的限制了。这里有两种不同的方法

方法 1

我们考虑对于两棵树上的同一个编号的点 $x,y$,他们需要满足 $a$ 相等。也就是 $out_{x}-in_{x}=out_{y}-in_{y}$。
把相同类型的整理一下可以得到 $out_{x}-out_{y}=in_{x}-in_{y}$。
减法很烦人 我们考虑如何搞成加法。我们显然有 $out_x+in_x=du_x$ ,那么继续有 $out_{x}+(in_{y}-du_y)=in_{x}+(out_{y}-du_y)$
这让我们想到用补集来刻画差。(说人话:让另一个数=1 往上连,=-1 往下连 也就是反过来)。
这样一顿操作后我们发现限制就变成了 $in_{x}+in_y=out_x+out_y$。于是我们把两个点所有的边都合并起来 求一个欧拉回路(也就是求出了一组满足条件的解),最后直接在某一棵树上分配即可。注意要好好记录边的方向(是记录向下和向上 不是记录是否反向 QAQ)
Code:

鉴于作者水平很低 代码可能和题解描述相反

const int MAXN = 2e5 + 5;

struct Edge{
    int to,w,nxt;    
}e[MAXN<<1];
int head[MAXN],cnt = 1;
int used[MAXN<<1];//1 正 2 反
int bk[MAXN];
inline void add(int u,int v,int w){
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,w,head[v]};head[v] = cnt;
}

inline void dfs(int v){
    for(int &i = head[v];i;i = e[i].nxt){
        if(used[e[i].w]) continue;
        used[e[i].w] = 1+(i&1);
        dfs(e[i].to);
    }
}

std::vector<int> G[MAXN];
std::vector<P> edge;
int du[MAXN];
std::vector<int> T1[MAXN],T2[MAXN];
int sm[MAXN],val[MAXN],n,rt1,rt2;

inline void Dfs(int v,int opt){
    sm[v] = val[v];
    for(auto x:(opt?T2:T1)[v]){
        Dfs(x,opt);sm[v] += sm[x];
    }
}

inline bool check(){
    Dfs(rt1,0);
    FOR(i,1,n) if(std::abs(sm[i]) != 1) return 0;
    Dfs(rt2,1);
    FOR(i,1,n) if(std::abs(sm[i]) != 1) {DEBUG(i);return 0;}
    return 1;
}

int main(){
    #ifdef RainAir
    freopen("aa.in","r",stdin);
    freopen("aa.out","w",stdout);
    #endif
    scanf("%d",&n);//DEBUG(n);
    FOR(i,1,n){
        int f;scanf("%d",&f);
        if(f == -1) rt1 = i;
        else add(f,i,i),du[i]++,du[f]++;
        if(f != -1) T1[f].pb(i),G[f].pb(i);
    }
    FOR(i,1,n){
        int f;scanf("%d",&f);
        if(f == -1) rt2 = i;
        else add(f,i,n+i),du[i]++,du[f]++;
        if(f != -1) T2[f].pb(i);
    }
    add(n+1,rt1,2*n+1);add(n+1,rt2,2*n+2);
    ++du[rt1];++du[rt2];
    FOR(i,1,n) if(du[i]&1) {puts("IMPOSSIBLE");return 0;}
    puts("POSSIBLE");
    FOR(i,1,n+1) bk[i] = head[i];
    dfs(n+1);
    FOR(i,1,n){
        int ans = 0;
        int ru=0,chu=0;
        for(auto x:G[i]) ans += used[x]==1?1:-1;
        int opt = i==rt1?used[2*n+1]:used[i];
        if(opt == 1) ans = 1-ans;
        else ans = -1-ans;
        printf("%d ",val[i] = ans);
    }
    return 0;
}

方法 2

回到分叉的地方 注意这个式子:$out_x-in_x+a_x=0$。
$out$ 和 $in$ 可以和边有关系 我们想让 $a_x$ 也和边有关系。
首先我们可以很轻易的得到当前这个点的奇偶性。

引理 1:如果有解,那么一定存在一种合法方案 满足点权只有1,0,-1

证明:和是 $1,-1$,如果出现了过于小的肯定会出现过于大的(或者是剩下的和加起来过于大的) 调整即可。
奇偶性不同显然无解。
如果是偶数 就只可能是 $0$。
奇数(也就是奇点)我们在两棵树上连一下对应的这两个点 由这个边的方向决定这个点的权值即可。
代码没写就不放了。

总结

  1. $a_x-b_x=a_y-b_y$ 型限制可以考虑对某一个取补集转化后变成加法 当然两者之间都是可以互相转化的
  2. 欧拉回路可以看成解某种限制的过程,所以出现只有两种状态的题的时候要么考虑 2-SAT 要么考虑欧拉图

版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/1055/

转载时须注明出处及本声明

Last modification:April 17th, 2020 at 12:26 am
如果觉得我的文章对你有用,请随意赞赏