很巧妙的一道题。对于一个点,如果它不是割点,那么去掉之后,它的答案一定是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 ; }