Educational Codeforces Round 132 (Rated for Div. 2) E. XOR Tree

E. XOR Tree

题意：

给定一棵树，每个结点有权值$a[i]$，如果树上任意两个结点之间的简单路径上的权值异或和不为0，则称这颗树是好的。问：至少修改几个结点的权值（可修改为任意数）使该树是一颗好树。

分析：

任意一条$u-$>$v$的路径的异或和为$sum[u]\wedge sum[v]\wedge a[lca(u,v)]$，$lca(u,v)$为$u，v$的最近公共祖先。因此如果存在$sum[u]\wedge sum[v]=a[x]，x=lca(u,v)$，则说明在$x$的子树中至少有一个结点需要修改。因为可以修改的值是任意的，所以如果要修改某个结点，那么该结点所经过的简单路径可以不用再考虑（直接当这个子树不存在）。
那么我们容易想到，修改$x$这个结点是最优的选择。
对于每个结点$x$，先处理其子树，如果子树中存在两个结点的异或和等于$a[x]$，则直接删除$x$结点，答案+1。否则我们就将这个子树合起来，合并过程中采用启发式合并优化，可以使复杂度降到$log$。

code:

int n, m, a[N];
int b[N], ans;
set<int> st[N];
vector<int> g[N];
void dfs(int u, int fa) {
    
    b[u] = a[u];
    if(fa != -1) b[u] ^= b[fa];
    for(int i : g[u]) {
    
        if(i != fa) {
    
            dfs(i, u);
        }
    }
}
void cals(int u, int fa) {
    
    bool f = 0;
    st[u].insert(b[u]);
    for(int i : g[u]) {
    
        if(i != fa) {
    
            cals(i, u);
            if(st[u].size() < st[i].size()) swap(st[u], st[i]);
            for(auto t : st[i]) f |= st[u].count(a[u] ^ t);
            for(auto t : st[i]) st[u].insert(t);
        }
    }
    if(f) {
    
        ans++;
        st[u].clear();
    }
}
void solve() {
    
    re(n); 
    for(int i = 0; i < n; i++) re(a[i]);
    for(int i = 0; i < n - 1; i++) {
    
        int x, y; re(x), re(y);
        x--; y--;
        g[x].pb(y); g[y].pb(x);
    }
    dfs(0, -1);
    cals(0, -1);
    cout << ans << '\n';
}