Codechef TAPAIR Counting the important pairs 随机化、树上差分

传送门

题意：给出一个$N$个点、$M$条边的无向连通图，求有多少组无序数对$(i,j)$满足：割掉第$i$条边与第$j$条边之后，图变为不连通。$N \leq 10^5 , M \leq 3 \times 10^5$

竟然随机化，歪果仁的思想好灵活qwq肯定是数据结构做多了

看起来很像割边，考虑$tarjan$，但是边三连通分量并不是很好实现，而且有很多特殊情况需要判断，所以我们考虑另外的算法

考虑$tarjan$时建出的一棵树。对于它来说，在一个端点在其下方、另一个端点在其上方的的返祖边可以成为它的依靠，因为割掉它，这一条依靠边可以代替它的功能。而对于一条返祖边来说，割掉对于树边是没有影响的，我们就定义它自己为自己的依靠。

这样每一条边都有自己的依靠集合。考虑两条依赖集合相同的边，将它们割掉之后，中间一段的点就会因为上下都没有额外的依靠而使得图不连通。而对于一条依赖集合为空的边（即割边），它选择任何边都可以加入贡献。

所以我们现在需要考虑如何给某一段边加入贡献。然后CC的题解给出的玄学办法是：随机化+树上差分+XOR

我们考虑将给一条返祖边定权值为一个$random$出来的值$t$，然后把所有依靠它的边的依靠集合异或上这个值，这个可以树上差分去做。这样所有的依靠集合就变成了一个数。然后我们判断两条边的依靠集合对应的数是否相等即可。

Because 2^64 is large enough comparing to the range of N and M, don’t worry about the probability. 🙂 You will get AC if you implemented correctly.——原题题解

然而我$rand() WA$了好几发qwq

如果随机数种子出了问题的话就看下面这种玄学rand好了

 #include<bits/stdc++.h>
 #define CC
 using namespace std; inline int read(){
     int a = ;
     bool f = ;
     char c = getchar();
     while(c != EOF && !isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(c != EOF && isdigit(c)){
         a = (a << ) + (a << ) + (c ^ '');
         c = getchar();
     }
     return f ? -a : a;
 } const int MAXN = ;
 struct Edge{
     int end , upEd;
 }Ed[MAXN * ];
 int head[MAXN] , num[MAXN] , dep[MAXN] , fa[MAXN] , N , cntEd , cnt;
 unsigned long long point[MAXN] , forS[MAXN * ];
 bool vis[MAXN]; #define ll unsigned long long
 inline ll rp(){return (1ll*rand())^(1ll*rand())<<^(1ll*rand())<<^(1ll*rand())<<^(1ll*rand())<<;} inline void addEd(int a , int b){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     head[a] = cntEd;
 } void dfs1(int x , int t){
     fa[x] = t;
     dep[x] = dep[fa[x]] + ;
     vis[x] = ;
     for(int i = head[x] ; i ; i = Ed[i].upEd)
         if(!vis[Ed[i].end])
             dfs1(Ed[i].end , x);
         else
             if(dep[Ed[i].end] > dep[x]){
                 long long t = rp();
                 point[x] ^= t;
                 point[Ed[i].end] ^= t;
                 forS[++cnt] = t;
             }
 } void dfs2(int x){
     for(int i = head[x] ; i ; i = Ed[i].upEd)
         if(fa[Ed[i].end] == x){
             dfs2(Ed[i].end);
             point[x] ^= point[Ed[i].end];
         }
     if(x != )
         forS[++cnt] = point[x];
 } int main(){
 #ifdef CC
     freopen("TAPAIR.in" , "r" , stdin);
     freopen("TAPAIR.out" , "w" , stdout);
 #endif     N = read();
     int M = read();
     for(int i =  ; i <= M ; i++){
         int a = read() , b = read();
         addEd(a , b);
         addEd(b , a);
     }
     dfs1( , );
     dfs2();
     sort(forS +  , forS + cnt + );
     int p = ;
     while(p <= cnt && forS[p] == )
         p++;
     long long ans = (p - ) * (long long)(p - ) /  + (p - ) * (M - p + );
     while(p <= cnt){
         int beg = p;
         while(p <= cnt && forS[p] == forS[beg])
             p++;
         ans += (long long)(p - beg) * (p - beg - ) / ;
     }
     cout << ans;
     return ;
 }