求无向图分别删去每个点后不连通的点对数。

 

首先，对于任何一个点，它本身删了，就会和剩下的n-1个点不连通，点对是有序的，所以初始答案为(n-1)*2

接下来考虑一些删去后能使原图分裂的点，也就是割点，它们带来的额外贡献就是 π(分裂出的几个连通块大小)*2，考虑如何求连通块数。

这里卡住了，看了sol..看来对tarjan的理解还是不够深

 

在原搜索树上记录子树siz[v]，记sum=Σsiz[v]，所以父亲那边的点就是n-sum-1个（减去自己），现在考虑这些连通块的贡献。

子树之间互相不连通，产生sum*siz[v]的贡献（sum晚一步更新，保证不重不漏），这样就可以计算子树间的贡献了。

然后计算父亲和子树们的贡献，就是siz[fa]*sum，此时sum已经更新为了整个子树的大小，siz[fa]=n-sum-1

 

时间复杂度O(n)

 

今天突然好困qwq

#include
     
      #include
      
       using namespace std;inline int rd() {    int ret=0,f=1;    char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}const int MAXN=100005;int n,m;struct Edge {    int next,to,w;} e[MAXN*10];int ecnt,head[MAXN];inline void add(int x,int y) {    e[++ecnt].next = head[x];    e[ecnt].to = y;    head[x] = ecnt;}int dfn[MAXN],low[MAXN],tim;long long siz[MAXN],ans[MAXN];void tarjan(int x) {    dfn[x]=low[x]=++tim;    siz[x]=1;    long long sum=0;    for(int i=head[x]; i; i=e[i].next) {        int v=e[i].to;        if(!dfn[v]) {            tarjan(v);siz[x]+=siz[v];            low[x]=min(low[x],low[v]);            if(dfn[x]<=low[v]) {                ans[x]+=sum*siz[v];                sum+=siz[v];            }        } else{            low[x]=min(low[x],dfn[v]);        }    }    ans[x]+=sum*(n-sum-1);}int main() {    n=rd();    m=rd();    int x,y,w;    for(int i=1; i<=m; i++) {        x=rd();        y=rd();        add(x,y);        add(y,x);    }    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);    for(int i=1;i<=n;i++) ans[i]+=n-1;    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]<<1);    return 0;}