在Byteotia有 n n 个城镇。 一些城镇之间由无向边连接。 在城镇外没有十字路口,尽管可能有桥,隧道或者高架公路(反正不考虑这些)。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。 每个城镇都有一个公民,他们被孤独所困扰。事实证明,每个公民都想拜访其他所有公民一次(在主人所在的城镇)。所以,一共会有次拜访。
不幸的是,一个程序员总罢工正在进行中,那些程序员迫切要求购买某个软件。
作为抗议行动,程序员们计划封锁一些城镇,阻止人们进入,离开或者路过那里。
正如我们所说,他们正在讨论选择哪些城镇会导致最严重的后果。
编写一个程序:
读入Byteotia的道路系统,对于每个被决定的城镇,如果它被封锁,有多少访问不会发生,输出结果。
第一行读入 n n ,,分别是城镇数目和道路数目
城镇编号 1∼n 1 ∼ n
接下来 m m 行每行两个数字,表示 a a 和之间有有一条无向边
输出 n n 行,每行一个数字,为第个城镇被锁时不能发生的访问的数量。
@[chen_zhe](/space/show?uid=8457)
翻译提供者:Park
5 5
1 2
2 3
1 3
3 4
4 5
8
8
16
14
8
今天考试考了这道题, 然而并没有看出这道题的 O(N) O ( N ) 做法, 自己yy了一个大概是 O(Nlog(N)) O ( N l o g ( N ) ) 的:求出割点后按割点拓扑序排序再树形dp一下求出每个割点每个子树的大小…然而觉得太麻烦就写了 N2 N 2 大暴力…
然而我还是太 naive n a i v e 了…
考虑乘法分配率…我们在求割点的时候每当求到一个子树
S
S
, 我们便可记录下这个子树的, 并统计一次贡献为
size×(N−size)
s
i
z
e
×
(
N
−
s
i
z
e
)
。
DFS
D
F
S
完成时, 若这个点是割点, 则我们已经统计了两次割下子树间的贡献, 一次割点对其他点的贡献, 一次割下子树对连通区域的贡献, 所以我们还要把答案加上
(N−∑size−1)×(∑size+1)+N−1
(
N
−
∑
s
i
z
e
−
1
)
×
(
∑
s
i
z
e
+
1
)
+
N
−
1
如果不是割点就更好办了, 答案就是 (N−1)×2 ( N − 1 ) × 2 (因为只有当前点被封锁的时候会对其他点有两次贡献)。
代码如下:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cctype>
#define R register
#define IN inline
#define gc getchar()
#define W while
#define MX 100050
#define ll long long
template <class T>
IN void in(T &x)
{
x = 0; R char c = gc;
W (!isdigit(c)) c = gc;
W (isdigit(c))
x = (x << 1) + (x << 3) + c - 48, c = gc;
}
struct Edge
{
int to, nex;
}edge[MX << 4];
int dot, line, cnt, arr, t;
int head[MX], dfn[MX], low[MX];
ll siz[MX], ans[MX];
bool cut[MX];
IN void addedge(const int &from, const int &to)
{
edge[++cnt] = {to, head[from]}, head[from] = cnt;
}
void tarjan(const int &now)
{
dfn[now] = low[now] = ++arr;
siz[now] = 1; ll sub = 0; int ct = 0;
for (R int i = head[now]; i; i = edge[i].nex)
{
if(!dfn[edge[i].to])
{
tarjan(edge[i].to);
siz[now] += siz[edge[i].to];
low[now] = std::min(low[now], low[edge[i].to]);
if(dfn[now] <= low[edge[i].to])
{
sub += siz[edge[i].to];
ans[now] += siz[edge[i].to] * (dot - siz[edge[i].to]);
if(now != 1 || ++ct > 1) cut[now] = true;
}
}
else low[now] = std::min(low[now], dfn[edge[i].to]);
}
if(!cut[now]) ans[now] = dot - 1 << 1;
else ans[now] += (sub + 1) * (dot - sub - 1) + dot - 1;
}
int main(void)
{
int a, b;
in(dot), in(line);
for (R int i = 1; i <= line; ++i)
in(a), in(b), addedge(a, b), addedge(b, a);
tarjan(1);
for (R int i = 1; i <= dot; ++i) printf("%lld\n", ans[i]);
}