2020牛客暑期多校训练营（第五场）B

题目描述

  Mr. W got a new graph with vertices and edges. It's a connected graph without cycles. Each edge should have an ugly value. To make the graph more beautiful, Mr. W hope you can help him modify it. You can delete or add one edge with an ugly value at a time and you can do it as many times as you want. But the following conditions should be satisfied at any time. The graph is connected. For each cycles in the graph, the XOR sum of all ugly values in the cycle is .
  Mr. W wants to know the minimum sum of ugly values of all edges in the graph.

输入描述

The first line contains one integer .
Next lines each contains three integers , denoting an edge between vertex and with ugly value .

输出描述

  One integer, the minimum sum of ugly values of all edges in the graph.

示例1

输入

6
0 1 1
1 2 4
1 3 3
0 4 5
0 5 2

输出

7

分析

  可以发现任意两个点之间连边的权值都是固定的。由于图始终连通，所以两点间始终存在至少一条路径，如果存在多条，根据环的异或和为 ，两点间的路径的异或和应该相等，且始终是固定的。在初始状态，设根节点（设为 ）到节点 路径的异或和为 ，那么若要在 之间添加一条边，为满足环的异或和为 ，其边权必须为 。
  可以视为： 个节点的完全图中，节点 的点权为 ，两点间的边权为两点权的异或值接下来。如此一来，预处理点权 后，就转化为求解异或最小生成树的问题，可以参考异或最小生成树模板题：CF888G。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第五场） Problem B
Date: 8/20/2020
Description: Minimum XOR Spanning Tree
*******************************************************************/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200004;
struct E
{
    int to;
    int w;
    int Next=-1;
}edge[N<<1];
ll ans=0;
int n;
bool vis[N];
int trie[N*30][2];
int head[N];
int dis[N];
int tot;
int num;
void bfs();//预处理dis
inline void add_edge(int,int,int);
//=================================
//异或最小生成树模板
void insert(int);
void dfs(int,int);
ll f(int,int,int);
//=================================
int main(){
    int i;
    cin>>n;
    memset(head,-1,sizeof(head));
    for(i=1;i<=n-1;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        u++;
        v++;
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    bfs();
    //init(1,0);
    for(i=1;i<=n;i++){
        insert(dis[i]);
    }
    dfs(0,30);
    cout<<ans<<endl;
    return 0;
}
void bfs(){
    queue<int>q;
    q.push(1);
    vis[1]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(register int i=head[x];~i;i=edge[i].Next){
            int y=edge[i].to;
            if(vis[y]){
                continue;
            }
            vis[y]=1;
            q.push(y);
            dis[y]=dis[x]^edge[i].w;
        }
    }
}
void insert(int x){
    int p=0;
    for(register int i=30;i>=0;i--){
        int ch=(x>>i)&1;
        if(!trie[p][ch]){
            trie[p][ch]=++tot;
        }
        p=trie[p][ch];
    }
}
void dfs(int p,int bit){
    if(bit<0){
        return;
    }
    if(trie[p][0]&&trie[p][1]){
        ans+=f(trie[p][0],trie[p][1],bit-1)+(1<<bit);
    }
    if(trie[p][0]){
        dfs(trie[p][0],bit-1);
    }
    if(trie[p][1]){
        dfs(trie[p][1],bit-1);
    }
}
ll f(int p1,int p2,int bit){
    if(bit<0){
        return 0;
    }
    ll res1=-1,res2=-1;
    if(trie[p1][0]&&trie[p2][0]){
        res1=f(trie[p1][0],trie[p2][0],bit-1);
    }
    if(trie[p1][1]&&trie[p2][1]){
        res2=f(trie[p1][1],trie[p2][1],bit-1);
    }
    if(res1>=0&&res2>=0){
        return min(res1,res2);
    }
    if(res1>=0){
        return res1;
    }
    if(res2>=0){
        return res2;
    }
    if(trie[p1][0]&&trie[p2][1]){
        res1=f(trie[p1][0],trie[p2][1],bit-1)+(1<<bit);
    }
    if(trie[p1][1]&&trie[p2][0]){
        res2=f(trie[p1][1],trie[p2][0],bit-1)+(1<<bit);
    }
    if(res1>=0&&res2>=0){
        return min(res1,res2);
    }
    if(res1>=0){
        return res1;
    }
    if(res2>=0){
        return res2;
    }
}
inline void add_edge(int u,int v,int w){
    num++;
    edge[num].to=v;
    edge[num].w=w;
    edge[num].Next=head[u];
    head[u]=num;
}