Educational Codeforces Round 132 (Rated for Div. 2) E. XOR Tree（启发式合并+贪心）

题目

n(n<=2e5)个点的树，点i权值ai（1<=ai<2^30）

修改最少的点的权值，使得树上不存在异或和为0的简单路径，输出最少的点数

权值可以被修改成任意正整数（可以是无限大）

思路来源

官方题解 & zlt题解

题解

假设树形是固定的，dfs往上回溯的时候，

如果一条路径xor为0，这条路径上必须改一个值，

贪心地来看，lca必须要改

由于可以改成任意值，改lca视为把这棵子树断掉

XOR(u,v) = XOR(根到u) xor XOR(根到v) xor a[lca(u,v)]

那就是判一下某个点的子树是否存在两个点的祖先异或，等于本身的权值

这个可以启发式合并的时候，把小的集合往大的集合上挂的时候判断

删除某个点，就可以认为是清空集合

心得

自己的写法怎么写都写不对，都wa8，感觉是启发式合并公有map导致的

只能抄官方题解，每个节点维护一个set了

代码

#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<set>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> P;
#define fi first
#define se second
#define pb push_back
const int N=2e5+10,INF=0x3f3f3f3f,mod=1e9+7;//998244353
int n,x,y,ans;
set<int>now[N];
int a[N],sz[N];
bool ban[N];
vector<int>E[N];
void dfs(int u,int fa,int w){bool ban=0;now[u].insert(w);for(auto &v:E[u]){if(v==fa)continue;dfs(v,u,w^a[v]);if(now[u].size()<now[v].size())now[u].swap(now[v]);for(auto &x:now[v]){if(now[u].count(x^a[u])){ban=1;break;}}for(auto &x:now[v]){now[u].insert(x);}now[v].clear();}if(ban){now[u].clear();ans++;}
}
int main(){scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);}for(int i=2;i<=n;++i){scanf("%d%d",&x,&y);E[x].push_back(y);//E[i].pb(P(fa,w));E[y].push_back(x);//E[i].pb(P(fa,w));}dfs(1,0,a[1]);printf("%d\n",ans);return 0;
}