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

E. XOR Tree

The question ：

Given a tree , Each node has a weight $a[i]$, If the exclusive or sum of the weights on the simple path between any two nodes in the tree is not 0, Call this tree good . ask ： At least modify the weights of several nodes （ Can be modified to any number ） Make the tree a good tree .

analysis ：

Any one of them $u-$>$v$ The exclusive or sum of paths of is $sum[u]\wedge sum[v]\wedge a[lca(u,v)]$,$lca(u,v)$ by $u,v$ The latest public ancestor of . So if there is $sum[u]\wedge sum[v]=a[x],x=lca(u,v)$, It's in $x$ At least one node in the subtree of needs to be modified . Because the value that can be modified is arbitrary , So if you want to modify a node , Then the simple path that the node passes through can be ignored （ Directly when this subtree does not exist ）.
Then it's easy for us to think , modify $x$ This node is the best choice .
For each node $x$, Process its subtree first , If the XOR sum of two nodes in the subtree is equal to $a[x]$, Then delete $x$ node , answer +1. Otherwise, we will combine this subtree , Heuristic merging optimization is adopted in the merging process , It can reduce the complexity to $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';
}