题解 SP15577 【STC10 - Blockade】

本题题解同[BLO-Blockade](https://www.luogu.org/problemnew/show/P3469) # ~~又是Tarjan!!!~~ 显然，删除后不影响整个图联通性的点，删除以后只会影响到它这个点和从它这个点出发的访问，即答案为`2*(n-1)`。 而删除后影响整个图联通性的点（即割点），删除后必定会把图分成2块及以上，显然这些块之间不能互相访问。则删除该点后阻止的访问数就是所有块的大小两两相乘再乘2. ~~为了防止遇到菊花图卡vector存块,~~ 令块的大小分别为A,B,C,D... 则答案为:$2(AB+AC+AD+...+BC+BD+...+CD+...)$ 化简得 $2[A(B+C+D+...)+B(C+D+...)+C(D+...)]$ 把小括号里的数用一个变量sum里，每次Tarjan完子树后计算`ANS += SIZE * sum * 2;sum += SIZE`即可。 ``` #include <bits/stdc++.h> using namespace std; const int N = 100005,M = 500005; int n,m,head[N],v[M * 2],nxt[M * 2],ptr,t1,t2; int dfn[N],low[N],index_p; long long ans[N]; bool cut_point[N]; void add_edge(int uu,int vv) { v[ptr] = vv;nxt[ptr] = head[uu];head[uu] = ptr++; } int tarjan(int pos,int dad) //返回树中的子结点数量 { dfn[pos] = low[pos] = ++index_p; int cnt = 0; long long sum = 0;int ret = 1; for (int i = head[pos];i != -1;i = nxt[i]) { if (!dfn[v[i]]) { long long child_cnt = tarjan(v[i],pos);ret += child_cnt; ++cnt; low[pos] = min(low[pos],low[v[i]]); if (low[v[i]] >= dfn[pos]) //这是一个割点 { ans[pos] += child_cnt * sum * 2;sum += child_cnt; } } else { low[pos] = min(low[pos],dfn[v[i]]); } } ans[pos] += sum * (n - 1 - sum) * 2;//最后计算时不能漏掉不是点pos的子树的其它点 return ret; } int main () { scanf("%d%d",&n,&m); memset(head,-1,sizeof(head));memset(nxt,-1,sizeof(nxt)); for (int i = 1;i <= m;i++) { scanf("%d%d",&t1,&t2);add_edge(t1,t2);add_edge(t2,t1); } tarjan(1,-1); for (int i = 1;i <= n;i++) { ans[i] += 2 * (n - 1);printf("%lld\n",ans[i]); } return 0; } ``` ### 因为我们特殊的计算方式，根的割点不用特判