CF1592C Bakry and Partitioning 题解

· · 题解

显然只会分成 2 个或 3 个连通块，因为更多的都可以以 -2 为低压缩（异或的性质，两个相同的数异或值为 0）。

如果是分成 2 个连通块，那么总异或和肯定为 0。并且，如果总异或和为 0，显然可以分成 2 个连通块。因此如果总异或和为 0 直接输出 YES 就可以了。

然后就是总异或和不为 0 的情况。显然此时不能分成 2 个连通块，只能分成 3 个连通块，并且如果总异或和为 sum，则分成的 3 个连通块的异或和均为 sum。

考虑如何处理这个过程。显然，分成 3 个连通块等价于删掉 2 条边，我们自底向上 DFS，如果 DFS 到某个点 u 的时候，以 u 为根的子树的异或和为 sum，说明可以在 u 到 fa 之间切割，那么这个时候令全局变量 cnt \gets cnt+1，然后令以 u 为根的子树的异或和为 0，即假装这个子树已经被切割不复存在。

最终判断是否 cnt \ge 2，是则输出 YES 否则输出 NO。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
int T,n,k,St,Ed,flag[N];
LL Ans;
vector<int> g[N];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
void DFS_init(int u,int fa){
    for(int v:g[u])if(v^fa)
        DFS_init(v,u),flag[u]=max(flag[u],flag[v]);
    return;
}
void DFS_sol(int u,int fa){
    for(int v:g[u])if(v^fa){
        if(flag[v]==1)DFS_sol(v,u),Ans+=2;
        if(flag[v]==2)DFS_sol(v,u),Ans+=1;
    }return;
}
int main(){
    T=read();
    while(T--){
        n=read(),k=read();
        St=read(),Ed=read();
        for(int i=1;i<=n;i++)g[i].clear(),flag[i]=0;
        for(int i=1;i<=k;i++)flag[read()]=1;
        flag[Ed]=2;
        for(int i=1;i<n;i++){
            int x=read(),y=read();
            g[x].pb(y),g[y].pb(x);
        }
        Ans=0;
        DFS_init(St,0);DFS_sol(St,0);
        cout<<Ans<<"\n";
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！