2020牛客暑期多校訓練營（第五場） B Graph

這題可以說就是cf888g改編了一下，加上有人賽中發題解，是以過了一百多人，實際上還是很難的

 首先我們要先明确一個東西：這個圖任意兩個點u，v邊權值始終不變，因為它所在的環異或和始終等于0，是以，邊uv的值就是這個環其他邊的異或和，現在即使它所在的環的某條邊x被删去了，由于圖要聯通，那x肯定是被它所在的另一個環的其他邊代替，而這些邊的異或和等于x的值，這其實相當于沒有删x，uv這條邊還是在一個同樣的環裡，權值必然不會變

現在我們就可以将每個點的值變成根節點到他的路徑異或和，uv連邊，邊值就是u點到v點路徑異或和，現在可以将原圖視為一個完全圖，uv邊值就是a[u]^a[v],我們最後還是要得到一顆樹，是以我們就是求這個完全圖的最小生成樹

這其實就是cf888g，可以參考我的另一篇部落格

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string>
#include<string.h>
#include<map>
#define ll long long
#include <iostream>
#include <math.h>
using namespace std;
#define maxn 3300000+5
ll tre[maxn][3],pos=0,sum[maxn];
struct node
{
    ll to,w;
};
vector<node>e[105000];ll a[maxn];
void add(ll x)
{
    ll c=0;
    for(ll i=30;i>=0;i--)
    {
        ll y=(x>>i)&1ll;
        if(!tre[c][y]) tre[c][y]=++pos;
        c=tre[c][y];
        sum[c]++;
    }
}
ll Find(ll x,ll y,ll step)
{
    ll ans=1e18;
    if(step==-1) return 0;
    if(tre[x][0])
    {
        if(tre[y][0])//也就是說，盡量保證左右兩邊數每位盡量一緻，這樣一緻異或就是0
        {
            ll w=Find(tre[x][0],tre[y][0],step-1);
            ans=w;
        }
        else
        {
            ll w=Find(tre[x][0],tre[y][1],step-1);
            ans=w+(1ll<<step);
        }
    }
    if(tre[x][1])
    {
        if(tre[y][1])//也就是說，盡量保證左右兩邊數每位盡量一緻，這樣一緻異或就是0
        {
            ll w=Find(tre[x][1],tre[y][1],step-1);
            ans=min(ans,w);
        }
        else
        {
            ll w=Find(tre[x][1],tre[y][0],step-1);
            ans=min(ans,w+(1ll<<step));
        }
    }
    //printf("tre[%lld][0]=%lld tre[%lld][1]=%lld tre[%lld][0]=%lld tre[%lld][1]=%lld step=%lld ans=%lld\n",x,tre[x][0],x,tre[x][1],y,tre[y][0],y,tre[y][1],step,ans);
    return ans;
}
ll dfs(ll c,ll step)
{
    ll ans=0;
    ll ls=sum[tre[c][0]],rs=sum[tre[c][1]];
        if(step==-1) return 0;
    if(tre[c][0])ans+=dfs(tre[c][0],step-1);
    if(tre[c][1])ans+=dfs(tre[c][1],step-1);
    if(min(ls,rs)>0)//隻有0和1都有才會分開連邊
    {
        ans+=Find(tre[c][0],tre[c][1],step-1)+(1ll<<step);//說明0和1都有，那它們0集合就要和1集合連邊，這條邊貢獻1<<step
                                                       //然後再在左右子樹找一個點對(也就是剩餘部分)，它們異或和最小
    }//printf("step=%lld tre[%lld][0]=%lld tre[%lld][1]=%lld ls=%lld rs=%lld ans=%lld\n",step,c,tre[c][0],c,tre[c][1],ls,rs,ans);

    return ans;

}
void init()
{
    pos=0;
}
void dfs0(ll u,ll fa)
{
    for(node i:e[u])
    {
        ll v=i.to,w=i.w;
        if(v==fa) continue;
        a[v]=a[u]^w;
        dfs0(v,u);
    }
}
int main()
{
    /*ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        ll x;
        scanf("%lld",&x);
        add(x);
    }
    ll ans=dfs(0,30);
    printf("%lld\n",ans);*/
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<n;i++)
    {
        ll u,v,w;
        scanf("%lld %lld %lld",&u,&v,&w);
        u++,v++;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    dfs0(1,-1);
    for(ll i=1;i<=n;i++)
    {
        add(a[i]);
    }
    ll ans=dfs(0,30);
    printf("%lld\n",ans);
}
/*
3
1 2 3
*/