[HOJ] 68 - 征服者

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
#define N 100005
vector<int> s[N];
int pre[N]={0},low[N],dfs_cnt={0},n;
long long int add[N]={0};
stack<int> sta;
long long int dfs(int u,int fa){
    int lowu,i;
    long long int tmp=1,p=1;
    lowu=pre[u]=++dfs_cnt;
    sta.push(u);
    for(i=0;i<s[u].size();i++){
        int v=s[u][i];
        if(pre[v]==0){
            long long int r=dfs(v,u);
            tmp+=r;
            lowu=min(lowu,low[v]);
            if(low[v]>=pre[u]){
                p+=r;
                add[u]+=r*(n-1-r);
            }
        }
        else if(pre[v]<pre[u] && v!=fa){
            lowu=min(lowu,pre[v]);
        }
    }
    add[u]+=(p-1)*(n-p);
    low[u]=lowu;
    return tmp;
}
int main(){
    int m,x,y,i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        s[x].push_back(y);
        s[y].push_back(x);
    }
    dfs(1,-1);
    for(i=1;i<=n;i++){
        printf("%lld\n",add[i]+(n-1)*2);
    }
}