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

题目大意

给一棵树，每条边有边权。可以任意加边和删边，但要满足任何时刻图连通，而且任何一个环的边权异或和为0。求操作后最小权值和。

解题思路

任意两个点之间连边的权值都是固定的，由于图需要始终联通，所以两点间始终存在至少一条路径，如果存在多条，根据环的异或和为0，两点间的路径的异或和应该相等，且始终是固定的。（摘自官方题解）

这样么，就可以每个点都记录一个权值，而两点间连边的权值，就是两端点权值的异或值。
接下来就是求异或最小生成树的问题了，使用Boruvka算法来解决是一种很吼的选择（学到了新的算法）。

Boruvka以及其他最小生成树算法：https://www.iteye.com/blog/dsqiu-1689178

而要让异或和最小，就要让二进制高位尽可能相等。
这样可以用到字典树来解决，连接两个点时，在这个节点的子树中找异或后最小的点对；为了保证得到的异或结果尽可能小，向下考虑走向时尽量方向相同。

AC代码

#include<bits/stdc++.h>
using namespace std;
struct link
{
    int x,y,z;
} e[200010];
int a[200010],b[6000010],c[6000010],d[100010],v[6000010][2],m[30],s=1,tot;
long long ans;
void get(int x,int y)
{
    for(int i=d[x];i;i=e[i].y)
        if(e[i].x!=y)
        {
            a[e[i].x]=a[x]^e[i].z;
            get(e[i].x,x);
        }
}
long long find(int x,int y)
{
    if(c[x]==30) return a[b[x]]^a[b[y]];
    bool f=0;
    long long z=2e9;
    if(v[x][0] && v[y][0]) z=min(z,find(v[x][0],v[y][0])),f=1;
    if(v[x][1] && v[y][1]) z=min(z,find(v[x][1],v[y][1])),f=1;
    if(!f)
    {
        if(v[x][0] && v[y][1]) z=min(z,find(v[x][0],v[y][1]));
        else if(v[x][1] && v[y][0]) z=min(z,find(v[x][1],v[y][0]));
    }
    return z;
}
void dfs(int x)
{
    if(!x) return;
    dfs(v[x][0]);dfs(v[x][1]);
    if(v[x][0] && v[x][1]) ans+=find(v[x][0],v[x][1]);
}
int main()
{
    int n,x,y,z,i,j;
    bool f;
    b[1]=m[0]=1;
    for(i=1;i<=29;i++)
        m[i]=m[i-1]*2;
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        x++,y++;
        e[++tot].x=y,e[tot].z=z,e[tot].y=d[x],d[x]=tot;
        e[++tot].x=x,e[tot].z=z,e[tot].y=d[y],d[y]=tot;
    }
    get(1,0);
    for(i=1;i<=n;i++)
    {
        x=1;
        for(j=29;j>=0;j--)
        {
            y=1<<j,f=y&a[i];
            if(!v[x][f]) v[x][f]=++s,c[s]=29-j+1,b[s]=n+1;
            x=v[x][f];
        }
        b[x]=i;
    }
    dfs(1);
    printf("%lld\n",ans);
    return 0;
}