LOJ 2587 「APIO2018」铁人两项

据说是圆方树模板题,但我卡了好久(

开幕感谢学姐Labelray教我这道题(祝她NOI Day2翻盘

本题要找一个三元组<s, c, f>,自然可以想到枚举端点s、f,求有几个中间点,也就是sf所在路径上有几个点。这个过程可以理解为在许多个BCC间走动,也就是在圆方树的方点间走动。

我们把方点的权值设为BCC的大小,方案数就是x到y路径上点的权值和。我们把圆点的权值设为-1,因为它们可能在多个BCC中出现,会重复统计。最后问题转化为求树上任意两点间距离权值和,这是一个树形DP的问题,当然我们也可以不DP,考虑每个点的贡献。

首先要注意的是所有点不一定联通,这可能是一个圆方树森林。因此我们每Tarjan完一次就来求一次答案。

我们设siz[x]为以x为根节点子树有多少圆点。有两种路径,一种是在x子树内两个点经过i,另一种是x子树内一个点与子树外一个点经过点x。

我们再设:y为x子树的根节点,tot为整棵圆方树的圆点数。需要注意的一点是这里的siz[x]是每处理一棵子树再加上去的,是截至目前已经处理过的x子树圆点数。

对于第一种,每个y对答案的贡献为siz[x] * siz[y] * val[x]。对于第二种,x的贡献为siz[x] * (num - siz[x]) * val[x]。这里的siz[x]已经处理完了。

注意只有ans开long long是不行的,右边也要强制转换。


代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

const int N = 200233;
struct Edge {int to, nxt;} e[N << 1], c[N << 1];
int head[N], hc[N], ecnt, ccnt, n, m, val[N], siz[N];
long long ans;

inline void AddEdge(int f, int to) {
e[++ecnt] = {to, head[f]}, head[f] = ecnt;
}

inline void AddC(int f, int to) {
c[++ccnt] = {to, hc[f]}, hc[f] = ccnt;
}

int dfn[N], low[N], stk[N], num, p, tot;

void Tarjan(int x) {
dfn[x] = low[x] = ++num, stk[++p] = x;
for (int i = head[x], y = e[i].to; i; i = e[i].nxt, y = e[i].to) {
if (!dfn[y]) {
Tarjan(y), low[x] = std::min(low[x], low[y]);
if (low[y] >= dfn[x]) {
AddC(++tot, x), AddC(x, tot); int z; val[tot]++;
do {
z = stk[p--], AddC(tot, z), AddC(z, tot), val[tot]++;
} while (y != z);
}
} else low[x] = std::min(low[x], dfn[y]);
}
}

void dfs(int x, int fa) {
if (x <= n) siz[x] = 1;
for (int i = hc[x], y = c[i].to; i; i = c[i].nxt, y = c[i].to)
if (y != fa)
dfs(y, x), ans += 1LL * siz[x] * siz[y] * val[x], siz[x] += siz[y];
ans += 1LL * siz[x] * (num - siz[x]) * val[x];
}

signed main() {
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; i++) {
scanf("%d%d", &x, &y);
AddEdge(x, y), AddEdge(y, x);
} tot = n;
for (int i = 1; i <= n; i++) val[i] = -1;
for (int i = 1; i <= n; i++)
if (!dfn[i]) num = 0, Tarjan(i), dfs(i, 0);
return !printf("%lld\n", ans << 1);
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×