2020牛客暑期多校训练营（第五场） B、Graph（字典树，最小生成树，思维）

题面：

题意：
给一棵树，每个边有边权，题目让你增减一些边，在操作的过程中保证：
（1）图是联通的
（2）图中任意的环的边权的异或值为 0
求任意操作后图中边权权值和最小值。

题解：
显然，任意两点直接相连的边权是固定值，为树上这两点简单路径上边权的异或和。而树上简单路径的边权异或和又可以转换成两点到根的前缀异或和的异或。那么问题就转换成了一个 n 个点的完全图的最小生成树。每个点有权值，边权就是边上两点的异或和。

我们可以很自然的建一棵 0/1 字典树，然后对于字典树上的每个节点，我们递归合并，它的最优情况一定是左右儿子中各取一个点连接到了一起，而且此时左子树里的点一定是在一个联通块中，右子树里也是在一个连通块中。我们进行启发式合并，假设当前左子树的大小小于右子树。那么我们枚举左子树中的所有点，然后去右子树中找与当前的点异或最小的点。单次合并的时间复杂度是 $O (n l o g n)$ 的，又我们进行的启发式合并，总复杂度是 $O (n l o g^{2} n)$ 的。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x7fffffff;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxp=1100;
const int maxm=4000100;
const int up=100000;

int t[maxn*31][2],si[maxn*31],cnt=0,rt=0;
int head[maxn],ver[maxn<<1],edge[maxn<<1],nt[maxn<<1],tot=1;
int val[maxn];
ll ans=0;

void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}

void _insert(int &p,int x,int k)
{
    if(!p) p=++cnt;
    if(k==-1)
    {
        si[p]=1;
        return ;
    }
    if(x&(1<<k)) _insert(t[p][1],x,k-1);
    else _insert(t[p][0],x,k-1);
    si[p]=si[t[p][0]]+si[t[p][1]];
}

void dfs(int x,int fa)
{
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i],z=edge[i];
        if(y==fa) continue;
        val[y]=val[x]^z;
        _insert(rt,val[y],30);
        dfs(y,x);
    }
}

int fimin(int p,int val,int k)
{
    if(k==-1) return 0;
    if(val&(1<<k))
    {
        if(t[p][1]) return fimin(t[p][1],val,k-1);
        else return fimin(t[p][0],val,k-1)+(1<<k);
    }
    else
    {
        if(t[p][0]) return fimin(t[p][0],val,k-1);
        else return fimin(t[p][1],val,k-1)+(1<<k);
    }
}

int _merge(int p1,int p2,int k1,int val,int k2)
{
    if(k1==-1) return fimin(p2,val,k2);
    int minn=inf;
    if(t[p1][0]) minn=min(minn,_merge(t[p1][0],p2,k1-1,val,k2));
    if(t[p1][1]) minn=min(minn,_merge(t[p1][1],p2,k1-1,val|(1<<k1),k2));
    return minn;

}

void dfsforans(int p,int k)
{
    if(!p) return ;
    dfsforans(t[p][0],k-1);
    dfsforans(t[p][1],k-1);
    if(!t[p][0]||!t[p][1]) return ;
    if(si[t[p][0]]<si[t[p][1]]) ans=ans+_merge(t[p][0],t[p][1],k-1,0,k-1)+(1<<k);
    else ans=ans+_merge(t[p][1],t[p][0],k-1,0,k-1)+(1<<k);
}

int main(void)
{
    int n,x,y,z;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    val[1]=0;
    _insert(rt,val[1],30);
    dfs(1,0);

    dfsforans(rt,30);

    printf("%lld\n",ans);
    return 0;

}