CUBE-T190: Supernova

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

typedef long long lli;
typedef pair<int, int> pii;

const int N = 1e5 + 5;

vector<pii> adj[N];
vector<int> cAdj[N];
pii edges[N];
int disc[N], low[N], isBridge[N], cVertex[N], dens[N], subTree[N], par[N];
lli ans[N];
bool visited[N];

int discCnt = 0;
void DFSBridge(int u, int pEdge){
    disc[u] = ++discCnt;
    low[u] = disc[u];
    visited[u] = true;
    for(pii nxt : adj[u]){
        int v = nxt.first;
        int i = nxt.second;
        if(i == pEdge){
            continue;
        }
        if(visited[v]){
            low[u] = min(low[u], disc[v]);
        } else {
            DFSBridge(v, i);
            low[u] = min(low[u], low[v]);
            if(low[v] > disc[u]){
                isBridge[i] = true;
            }
        }
    }
}

void DFSConnect(int u, int idx){
    cVertex[u] = idx;
    ++dens[idx];
    visited[u] = true;
    for(pii nxt : adj[u]){
        int v = nxt.first;
        int i = nxt.second;
        if(!visited[v] && !isBridge[i]){
            DFSConnect(v, idx);
        }
    }
}

void DFS(int u, int p){
    par[u] = p;
    int cnt = dens[u];
    for(int v : cAdj[u]){
        if(v == p){
            continue;
        }
        DFS(v, u);
        cnt += subTree[v];
    }
    subTree[u] = cnt;
}

int main(){

    int nVertex, nEdge;
    scanf("%d%d", &nVertex, &nEdge);
    for(int i = 1; i <= nEdge; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
        edges[i] = pii(u, v);
    }
    DFSBridge(1, 0);
    for(int u = 1; u <= nVertex; ++u){
        visited[u] = false;
    }
    int idx = 0;
    for(int u = 1; u <= nVertex; ++u){
        if(!visited[u]){
            DFSConnect(u, ++idx);
        }
    }
    for(int i = 1; i <= nEdge; ++i){
        if(isBridge[i]){
            int u = cVertex[edges[i].first];
            int v = cVertex[edges[i].second];
            cAdj[u].push_back(v);
            cAdj[v].push_back(u);
        }
    }
    DFS(1, 0);
    for(int i = 1; i <= nEdge; ++i){
        if(isBridge[i]){
            int u = cVertex[edges[i].first];
            int v = cVertex[edges[i].second];
            if(par[u] == v){
                swap(u, v);
            }
            ans[i] = (lli)subTree[v] * (nVertex - subTree[v]);
        } else {
            ans[i] = 0;
        }
    }
    for(int i = 1; i <= nEdge; ++i){
        cout << ans[i] << ' ';
    }

    return 0;
}