Codeforces Round #746 (Div. 2) C 按位异或 DFS 分块

题目

Bakry 遇到了一个问题，但由于他懒于解决，所以他请求您的帮助。

给定一个由 n 个节点组成的树，第 i 个节点为从 1 到 n 的每个 i 分配了值 ai。提醒一下，n 个节点上的树是具有 n-1 条边的连通图。

您想从树中删除至少 1 个，但最多 k-1 个边，以便以下条件成立：

对于每个连接的组件，计算其中节点值的按位异或。然后，对于所有连接的组件，这些值必须相同。

有没有可能达到这个条件？

输入
每个测试包含多个测试用例。第一行包含测试用例数 t (1≤t≤5⋅104)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 n 和 k (2≤k≤n≤105)。

每个测试用例的第二行包含 n 个整数 a1,a2,…,an (1≤ai≤109)。

接下来n-1行的第i行包含两个整数ui和vi（1≤ui，vi≤n，ui≠vi），这意味着节点ui和vi之间有一条边。

保证给定的图是一棵树。

保证所有测试用例的 n 总和不超过 2⋅105。

输出
对于每个测试用例，您应该输出一个字符串。如果根据上面写的条件可以删除边，输出“YES”（不带引号）。否则，输出“NO”（不带引号）。

您可以在任何情况下（上或下）打印“YES”和“NO”的每个字母。

题解思路

首先每个子树都是可以一刀切掉的。
如果所有节点的XOR值为 0 ，说明森林必然存在两个部分可以相等，切（任意）一条边即可，可以直接得出能操作。（这步属实有点难理解，但他是对的）

如果XOR不为0，如果能操作出的话，肯定是由3 5 7 个以上相等的分块来
XOR出的，而5个又可以合并成3个而不影响值。

所以我们只有找出3个以上的连通块（子树）并且K大于等于3即可。

这里用的DFS来解决，从1开始遍历每个节点并合并连通块，当连通块为XOR值的时候就置为0，不让他影响其他连通块。

递归的过程要好好理解。

AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const  int  INF =  0x3f3f3f3f;
const  int N = 200100 ;

int n , k , tot ,cucnt ;

int w[N] ;
int a[N] ;
vector  head[N];

void dfs(int cu , int fa )
{
    a[cu] = w[cu] ;
    for ( auto it : head[cu] )
    {
        if ( it == fa )
            continue;
        dfs(it , cu ) ;
        a[cu] ^= a[it] ;
    }
    if ( a[cu] == tot )
    {
        cucnt++;
        a[cu] = 0 ;
    }
}

int main ()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while( T -- )
    {
        cucnt = 0 ;
        int book = 0 ;
        cin >> n >> k ;
        tot = 0 ;
        for (int i = 1 ; i <= n ; i++ )
            head[i].clear();
        for (int i = 1 ; i <= n ; i++ )
        {
            cin >> w[i] ;
            tot ^= w[i] ;
        }
        for (int i = 1 ; i < n ; i++ )
        {
            int t1 , t2 ;
            cin >> t1 >> t2 ;
            head[t1].push_back(t2);
            head[t2].push_back(t1);
        }
        if ( tot == 0 )
            book = 1 ;
        else
            dfs(1,0);
        if ( cucnt >= 3 && k >= 3 )
            book = 1 ;
        if ( book )
            cout << "YESn" ;
        else
            cout << "NOn" ;
    }
    return 0 ;
}

Codeforces Round #746 (Div. 2) C 按位异或 DFS 分块

C/C++/C#相关栏目本月热门文章