[HOJ]68 征服者

割點好容易忘記...

#include<cstdio>
#include<vector>
#include<algorithm>
#define MAX 100005
using namespace std;
vector<int> v[MAX];
int n,m,fr,to,in[MAX],low[MAX],t;
long long cnt[MAX];
int dfs(int k,int pa){
    int ch=1,tmp,all=1,now,nt;
    now=in[k]=++t;
    for(int i=0;i<v[k].size();i++){
        nt=v[k][i];
        if(!in[nt]){
            tmp=dfs(nt,k);
            ch+=tmp;
            now=min(now,low[nt]);
            if(low[nt]>=in[k]){
                all+=tmp;
                cnt[k]+=(long long)(n-1-tmp)*tmp;
            }
        }
        else if(in[nt]<in[k]&&nt!=pa){
            now=min(now,in[nt]);
        }
    }
    low[k]=now;
    cnt[k]+=(long long)(all-1)*(n-all);
    return ch;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&fr,&to);
        v[fr].push_back(to);
        v[to].push_back(fr);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        printf("%lld\n",cnt[i]+2*n-2);
    }
}