可持久化动态广义仙人掌

难道没人发现这张图的名字叫做"xiaobo"吗

这道题思路很简单，首先可以知道这个"好边"就是图中的桥

于是可以想到把所有的边双缩点得到一张新图，这张图(树)上的所有剩余边均是桥，也就是"好边"

这时候我们连接任意两点就可以使这两点之间的所有的边("好边")不构成好边，而我们的目的是最小化"好边"数量

所以我们只需要连接这棵树的直径便可以了

*发发牢骚：nmd考场上思路是对的结果边双缩点倒闭了，只能拿$30pts$树分跑路了

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;

int idx, num, point, max_dis;
int dfn[N], low[N];
int tab[N];
bool vis[N], group[N<<2];
vector< int > sp_rode[N];
vector< pair< int,int > > rode[N];

void dfs( int p,int ine )
{
	dfn[p]=low[p]=++idx;
	for( auto [x,iidx]:rode[p] )
	{
		if( ine == iidx ) continue;
		if( !dfn[x] )
		{
			dfs( x,iidx^1 );
			low[p]=min( low[p],low[x] );
			if( low[x] > dfn[p] ) group[iidx]=group[iidx^1]=1;
		}	
		else low[p]=min( low[p],dfn[x] );
	}
}

void get_ans( int p )
{
    tab[p]=num;
	vis[p]=true;
	for( auto [x,iidx]:rode[p] )
	{
		if( vis[x] ) continue;
		if( group[iidx] ) continue; 
		get_ans( x );
	}
}

void get_d( int p,int fa,int dis )
{
	for( auto x:sp_rode[p] )
	{
		if( x == fa ) continue;
		get_d( x,p,dis+1 );
	}
	if( dis > max_dis ) max_dis=dis, point=p;
}

void intt( int n,int m )
{
    idx=num=0;
    for( int i=1;i<=n;i++ ) dfn[i]=low[i]=vis[i]=0;
	for( int i=1;i<=n;i++ ) rode[i].clear(), sp_rode[i].clear();
    for( int i=1;i<=m;i++ ) group[i<<1]=group[i<<1|1]=0;
}

void sovel()
{
	int n, m;
	cin>>n>>m;
    intt( n,m );
	for( int i=1, x, y;i<=m;i++ )
	{
		cin>>x>>y;
		rode[x].push_back( { y,i<<1 } ), rode[y].push_back( { x,i<<1|1 } );
	}
	for( int i=1;i<=n;i++ )
		if( !vis[i] )
			dfs( i,i );
    memset( vis,0,sizeof( vis ) );
	for( int i=1;i<=n;i++ )
		if( !vis[i] )
			num++, get_ans( i );
    int cnt=0;
    for( int u=1;u<=n;u++ )
        for( auto [v,iidx]:rode[u] )
            if( tab[u] != tab[v] )
                sp_rode[tab[u]].push_back( tab[v] ), cnt++;
    max_dis=-1;
    get_d( 1,1,0 );
    max_dis=-1;
    get_d( point,point,0 ); 
    cout<<cnt/2-max_dis<<"\n";
}

int main()
{	
	// freopen( "txt.in","r",stdin );
	std::ios::sync_with_stdio( false );
	cin.tie( nullptr );
	cout.tie( nullptr );
	int t;
	for( cin>>t;t;t-- ) sovel();
}