[APIO2018] Duathlon 铁人两项 圆方树，DP

[APIO2018] Duathlon 铁人两项

LG传送门

圆方树+简单DP。

不会圆方树的话可以看看我的另一篇文章。

考虑暴力怎么写，枚举两个点，答案加上两个点之间的点的个数。

看到题面中的一句话：

换句话说就是简单路径，用（广义）圆方树的基本条件已经满足，可以把问题变到树上：令方点的权值为所在点双的大小，圆点会被算重所以点权为\(-1\)，统计任意两点间的点权和就好了。直接做是\(n ^ 2\)的，考虑枚举每一个点看会产生多少贡献，对答案的贡献就乘个点权。

注意图不一定联通。

#include <cstdio>

#include <cctype>

#include <vector>

#define R register

#define I inline

#define B 1000000

#define L long long

using namespace std;

const int N = 200003;

char buf[B], *p1, *p2;

I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }

I int rd() {

    R int f = 0;

    R char c = gc();

    while (c < 48 || c > 57)

        c = gc();

    while (c > 47 && c < 58)

        f = f * 10 + (c ^ 48), c = gc();

    return f;

}

L ans = 0;

int s[N], w[N], dfn[N], low[N], vis[N], sta[N], siz[N], n, tim, cnt, stp, tot;

vector <int> g[N], G[N];

I int min(int x, int y) { return x < y ? x : y; }

void dfs(int x) {

    dfn[x] = low[x] = ++tim, sta[++stp] = x, w[x] = -1, ++tot;

    for (R int i = 0, y, z; i < s[x]; ++i)

        if (!dfn[y = g[x][i]]){

            dfs(y), low[x] = min(low[x], low[y]);

            if (low[y] >= dfn[x]) {

                w[++cnt] = 1, G[x].push_back(cnt), G[cnt].push_back(x);

                do {

                    z = sta[stp--], ++w[cnt], G[z].push_back(cnt), G[cnt].push_back(z);

                } while (z ^ y);

            }

        }

        else

            low[x] = min(low[x], dfn[y]);

}

void calc(int x, int f) {

    siz[x] = vis[x] = x <= n;

    L tmp = 0;

    for (R int i = 0, y, S = G[x].size(); i < S; ++i)

        if ((y = G[x][i]) ^ f)

            calc(y, x), tmp += 2ll * siz[y] * siz[x], siz[x] += siz[y];

    tmp += 2ll * siz[x] * (tot - siz[x]), ans += tmp * w[x];

}

int main() {

    freopen("a.in", "r", stdin);

    R int m, i, x, y;

    cnt = n = rd(), m = rd();

    for (i = 1; i <= m; ++i)

        x = rd(), y = rd(), g[x].push_back(y), g[y].push_back(x);

    for (i = 1; i <= n; ++i)

        s[i] = g[i].size();

    for (i = 1; i <= n; ++i)

        if (!vis[i])

            stp = 0, tot = 0, dfs(i), calc(i, 0);

    printf("%lld", ans);

    return 0;

}