很巧妙的一道题。对于一个点,如果它不是割点,那么去掉之后,它的答案一定是2*(n-1)(图的连通性没有改变)。如果这个点是割点,那么割掉之后会形成(设它有t个儿子)至多t+2个联通块(t个儿子,它本身,剩下的部分)。那么对于答案的贡献就是。另外注意中间值爆
#include <bits/stdc++.h>
namespace init {
#define ll long long
#define inf 0x3f3f3f3f
#define il inline
#define N 100010
}
namespace io {
#define in(a) a=read()
#define out(a) write(a)
#define outn(a) out(a),putchar('\n')
#define I_int int
inline I_int read() {
I_int x = 0 , f = 1 ; char c = getchar() ;
while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
return x * f ;
}
char F[ 200 ] ;
inline void write( I_int x ) {
if( x == 0 ) { putchar( '0' ) ; return ; }
I_int tmp = x > 0 ? x : -x ;
if( x < 0 ) putchar( '-' ) ;
int cnt = 0 ;
while( tmp > 0 ) {
F[ cnt ++ ] = tmp % 10 + '0' ;
tmp /= 10 ;
}
while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
}
#undef I_int
}
using namespace io ;
using namespace init ;
ll ans[N] ;
int dfn[N] , low[N] , siz[N] , tim ;
bool cut[N] ;
int n , m , root ;
int head[N] , cnt ;
struct edge {
int to , nxt ;
} e[1000010] ;
void ins(int u , int v) {
e[++cnt].to = v ;
e[cnt].nxt = head[u] ;
head[u] = cnt ;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ tim ; siz[u] = 1 ;
int flag = 0 , sum = 0 ;
for(int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].to ;
if(!dfn[v]) {
tarjan(v) ;
low[u] = std::min(low[u] , low[v]) ;
siz[u] += siz[v] ;
if(low[v] >= dfn[u]) {
flag ++ ;
ans[u] += (ll)siz[v] * (n - siz[v]) ;
sum += siz[v] ;
if(u != 1 || flag > 1) cut[u] = 1 ;
}
} else low[u] = std::min(low[u] , dfn[v]) ;
}
if(cut[u]) ans[u] += (ll)(sum + 1)*(n - sum - 1) + (n - 1) ;
else ans[u] = (n - 1) * 2 ;
}
int main() {
n = read() , m = read() ;
for(int i = 1 ; i <= m ; i ++) {
int a = read() , b = read() ;
ins(a , b) , ins(b , a) ;
}
tarjan(1) ;
for(int i = 1 ; i <= n ; i ++) printf("%lld\n" , ans[i]) ;
return 0 ;
} 
京公网安备 11010502036488号