洛谷P3469 [POI2008]BLO-Blockade

题目描述

There are exactly $n$ towns in Byteotia.

Some towns are connected by bidirectional roads.

There are no crossroads outside towns, though there may be bridges, tunnels and flyovers. Each pair of towns may be connected by at most one direct road. One can get from any town to any other-directly or indirectly.

Each town has exactly one citizen.

For that reason the citizens suffer from loneliness.

It turns out that each citizen would like to pay a visit to every other citizen (in his host's hometown), and do it exactly once. So exactly $n\cdot (n-1)$ visits should take place.

That's right, should.

Unfortunately, a general strike of programmers, who demand an emergency purchase of software, is under way.

As an act of protest, the programmers plan to block one town of Byteotia, preventing entering it, leaving it, and even passing through.

As we speak, they are debating which town to choose so that the consequences are most severe.

Task Write a programme that:

reads the Byteotian road system's description from the standard input, for each town determines, how many visits could take place if this town were not blocked by programmers, writes out the outcome to the standard output.

给定一张无向图，求每个点被封锁之后有多少个有序点对(x,y)(x!=y,1<=x,y<=n)满足x无法到达y

输入输出格式

输入格式：

In the first line of the standard input there are two positive integers: $n$ and $m$ ( $1\le n\le 100\ 000$ , $1\le m\le 500\ 000$ ) denoting the number of towns and roads, respectively.

The towns are numbered from 1 to $n$ .

The following $m$ lines contain descriptions of the roads.

Each line contains two integers $a$ and $b$ ( $1\le a<b\le n$ ) and denotes a direct road between towns numbered $a$ and $b$ .

输出格式：

Your programme should write out exactly $n$ integers to the standard output, one number per line. The $i^{th}$ line should contain the number of visits that could not take place if the programmers blocked the town no. $i$ .

输入输出样例

输入样例#1：复制

输出样例#1：复制

这道题要求删去一个点之后会减少多少个联通的点。我们的第一想法肯定是先缩点，然后向下dfs统计点数，那么每一个点的答案就是：所有子搜索树总大小之间两两之积的和。在这里我们处理“所有儿子两两之积的和”这个东西是有小技巧的。我们用一个数累加，每一次乘上当前的累加值并且将累加值加上当前子搜索树的大小。

比如：对一些子树size[4]{2, 3, 5, 3} 做操作

我们的s、ans先为0，然后ans += s * size[0], s += size[0]

s = 2, ans = 0 : ans += s * size[1], s += size[1]

s = 5, ans = 6 : ans += s * size[2], s += size[2]

s = 10, ans = 31 : ans += s * size[3], s += size[3]

最后s = 13, ans = 61，所以就O(n)算出了两两之积的和为61

#include<cstdio>
#include<queue>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 2e5 + 5;
const int maxm = 7e5 + 5;
struct edge {
    int v, next;
}e[maxm << 1];
int n, m, st, size[maxn];
long long ans[maxn];
int dfn[maxn], low[maxn], head[maxn], clk, cnt;
void adde(const int &u, const int &v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt;
}
int tarjan(int u, int fa) {
    LL s = 0;
    size[u] = 1;
    dfn[u] = low[u] = ++clk;
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa) continue;
        if(dfn[v]) low[u] = min(low[u], low[v]);
        else {
            low[u] = min(low[u], tarjan(v, u));
            size[u] += size[v];
            if(low[v] >= dfn[u])
                ans[u] += s * size[v], s += size[v];
        }
    }
    ans[u] += s * (n - s - 1);
    return low[u];
}

int main() {
    scanf("%d%d", &n, &m);
    int u, v;
    for(register int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        adde(u, v), adde(v, u);
    }
    st = 1;
    tarjan(st, 0);
    for(register int i = 1; i <= n; ++i) 
        printf("%lld\n", (ans[i] + (n - 1)) * 2LL);
    return 0;
}

Rockdu's Blog