HDU6350 always online

题意

给出一个 \(n\) 个点 \(m\) 条边的无向图，任意两点之间至多两条路径，以 \(flow(s,t)\) 表示 \(s\) ,\(t\) 两点之间的最大流，求 \(\sum_{1 \leq s < t \leq n} s \oplus t \oplus flow(s,t)\)。

题解

首先我们发现整个图实际上是一颗仙人掌,考虑简化一下。

如果整个图是一颗树我们应该怎么做?

很显然啊, \(flow(s,t)\) 就等于 \(s\) , \(t\) 之间的边权最小值,这很显然。

如果整个图是一颗基环树我们应该怎么做?

我们知道最大流等于最小割,假设我们求 \(s,t\) 之间有一个环,那割边显然有两种情况。
1.在非环的位置上割一条边，图会不联通。
2.在环上割两条边，图会不联通。
实际上就是有两条不同的路径可以到达，第一种情况没有什么特殊的。
第二种就比较特殊了，实际上删除不是任意删除两条边都可以的，这个要根据可达性来判断删除哪两条边。
但是可以发现环上边权最小的边一定会被优先割掉,这个证明起来并不难，另一条边就是要根据情况来割。
有一个比较厉害的思路，我们知道如果一个环被割,则边权最小的边一定会被割，所以我们选择不管。
我们在环上选择任意一条边权最小割掉，将这条边的权值加到这个环的其它边上，这样做有什么好处呢?
我们将环上的边的权值贡献常态化了，若是直接去做我们要根据不同的环去增加不同的值，但是直接加上了就不需要去管了。
所以将最小的边割掉之后就变成了一颗树了，按照第一种情况做就行了。

如果整个图是一颗仙人掌我们应该怎么做?

其实进阶的不是很多,仙人掌有性质,每条边至多只会被包含在一个环中，所以我们对每一个环都做以上操作，整个图也转化为树。
但是我们会发现即使这样，统计答案还是很困难，异或和最小值这两个东西很难搞。
乍一看是一个路径统计问题，想想能不能点分治，很遗憾，似乎十分困难。
换一种方式，我们枚举一条边能对哪些点集做贡献,我们将边从大到小排序,用并查集维护,一条边所联通的两个联通块就是它能做贡献的联通块。
这其实就是克鲁斯卡尔重构树的过程，现在最小值解决了，异或还是比较不寻常的。
直接异或显然是比较难的，我们选择拆位算贡献，我们对每个连通块记录大小和里面的数每一位有\(1\)的个数来计算就好了，这道题就解决了。

code

#include <bits/stdc++.h>
#define int long long
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
    x = 0 ;rg int f(0) ; rg char c(gc()) ;
    while(!isdigit(c)) f |= (c=='-'),c = gc() ;
    while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
    x = (f?-x:x) ;
    read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
    if(x < 0) pc('-'),x = -x ;
    do stk[++tp] = x%10,x /= 10 ; while(x) ;
    while(tp) pc(stk[tp--]^48) ; space ;
    print(p...) ;
}
const int N = 2e5+5 ;
int n,m,top ; unsigned int ans ;
int vis[N],vvs[N],del[N],sz[N],fa[N],st[N],num[N][35] ;
struct RP{int v,w,id ;}Edge[N*10],E[N*10] ;
vector<RP>e[N] ;
bool S_GND ;
void Solve(int x,int fa)
{
    vis[x] = 1 ;
    for(auto [v,w,id]:e[x]) if(!vvs[id])
    {
        vvs[id] = 1,st[++top] = id ;
        if(vis[v])
        {
            int mi = w,pos = top-1,op = 0 ;
            while(Edge[st[pos]].v != v && Edge[st[pos]].w != v) mi = min(mi,Edge[st[pos]].id),--pos ;
            mi = min(mi,Edge[st[pos]].id) ;
            ROF(i,top,pos,1) 
                if(!op && Edge[st[i]].id == mi) op = 1,del[st[i]] = 1 ;
                else Edge[st[i]].id += mi ;
        }
        else Solve(v,x) ; top-- ;
    }
}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]) ;}
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
	// freopen(".in","r",stdin) ;
	// freopen(".out","w",stdout) ;
    read(n,m) ;
    FOR(i,1,m,1)
    {
        int u,v,w ; read(u,v,w) ;
        Edge[i] = {u,v,w},e[u].pb({v,w,i}),e[v].pb({u,w,i}) ;
    }
    FOR(i,1,n,1)
    {
        fa[i] = i,sz[i] = 1 ;
        FOR(j,0,30,1) num[i][j] = (i>>j)&1 ;
    }
    Solve(1,0) ; FOR(i,1,m,1) if(!del[i]) E[i] = Edge[i] ;
    sort(E+1,E+1+m,[&](auto x,auto y){return x.id > y.id ;}) ;
    FOR(i,1,m,1)
    {
        auto [x,y,w] = E[i] ; x = get(x),y = get(y) ;
        FOR(j,0,30,1)
        {
            unsigned int res = 0 ;
            if((w>>j)&1) res += 1ull*num[x][j]*num[y][j]+1ull*(sz[x]-num[x][j])*(sz[y]-num[y][j]) ;
            else res += 1ull*(sz[x]-num[x][j])*num[y][j]+1ull*num[x][j]*(sz[y]-num[y][j]) ;
             ans += (1ull<<j)*res,num[y][j] += num[x][j] ;
        } sz[y] += sz[x],fa[x] = y ;
    }
    print(ans) ; //enter ;
    // FOR(i,1,m,1) print(del[i]) ; enter ;
    // FOR(i,1,m,1) print(Edge[i].id) ; enter ;
    return 0 ;
}