牛客多校第5场补题BGraph异或最小生成树

Graph

题目链接

题目大意

给出一颗树，有两种操作，添加一条边，删除一条边。
每个时刻必须满足
如果有环那么环的边权异或和必须是0，
必须是联通的。

题解

也就是先求一下每个节点到根节点的异或和，然后用这些值的异或当边权求个最小生成树。
问题就是 知道一些点的点权，边权是两个点权异或，然后求最小生成树。
求最小异或值可以用字典树。
好了，比赛的时候就想到了这里，不会求了。然后考虑到了并查集，但是不会两个集合合并，也就是合并n &＃8211; 1次，但是怎么求两个集合里的数各挑一个的异或最小值，然后就不会了好菜，连异或最小生成树都没听过

然后 异或最小生成树，可以这样求：
分治，从高位到低位考虑。最优肯定是：根据当前位分成这一位是1的和这一位是0的，左边合并完，右边合并完，然后 在左边找一个在右边找一个值合并，这样的话就可以把左边加到字典树里，遍历右边找最小的异或值。然后就相当于合并了。
显然合并了n &＃8211; 1次，符合。
代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){ freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){ freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){ return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){ a %= mod;ll ans = 1;while(b){ if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{ bool operator()(const pii & a, const pii & b){ return a.second < b.second;}};
int lb(int x){ return x & -x;}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxn = 1e5+5;
int dep[maxn];
std::vector<pii> vv[maxn];
void dfs(int x,int fa,int d)
{
dep[x] = d;
for (int i = 0; i < vv[x].size(); i ++ )
{
int v = vv[x][i].st;
if(v == fa)
continue;
dfs(v,x,d ^ vv[x][i].sd);
}
}
int tree[maxn * 30][2];
int cnt =0 ;
void add(int x)
{
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int f = x >> i & 1;
if(tree[p][f] == 0)
{
tree[p][f] = ++cnt;
}
p = tree[p][f];
// cout<
}
}
int query(int x)
{
int ans = 0;
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int f = x >> i & 1;
if(tree[p][f])
{
p = tree[p][f];
// cout<
}
else
{
p = tree[p][!f];
ans += 1 << i;
}
}
return ans;
}
int num[maxn];
bool cmp(int a,int b)
{
return a > b;
}
ll ans =0;
void fenzhi(int l,int r,int de)
{
// printf("%d %d %d\n",l,r,de);
if(l >= r || de < 0)
return;
int mid = l;
while(mid <= r && (dep[mid] >> de & 1) == 0)
{
mid ++ ;
}
fenzhi(l,mid - 1,de - 1);
fenzhi(mid,r,de - 1);
if(mid <= l || mid > r)
return;
for (int i = l; i < mid; i ++ )
{
add(dep[i]);
}
int temp = inf;
for (int i = mid; i <= r; i ++ )
{
temp = min(temp,query(dep[i]));
}
// printf("%d %d %d %d\n",l,mid,r,temp);
ans += temp;
for (int i= 0; i <= cnt; i ++ )
{
tree[i][0] = tree[i][1] = 0;
}
cnt = 0;
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 1; i < n; i ++ )
{
int x,y,val;
scanf("%d%d%d",&x,&y,&val);
vv[x].pb(mkp(y,val));
vv[y].pb(mkp(x,val));
}
dfs(0,0,0);
sort(dep,dep + n);
fenzhi(0,n - 1,30);
cout<<ans<<endl;
}