題目

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;
}