[Luogu 4630] APIO2018 铁人两项（广义圆方树）

铁人两项

求满足存在 $x\to y$ 和 $y\to z$ 的不相交简单路径的有序点对 $(x,y,z)$ 的方案数。

即，选择的路径只经过同一个点至多一次。

线性做法。

广义圆方树

可以解决一些“每个点至多经过一次”的问题。

对于任意无向图，都可以建出它的广义圆方树。

tarjan 求出每个点双连通分量，然后同一点双的所有点（圆点）向代表这个点双的点（方点）连边。

只考虑这些新连的边，发现在 广义圆方树 中，只有圆点和方点连的边，且这些新连的边恰好构成一棵树。

那么就在考虑点双的问题中，把原来的一般无向图转化为树，然后就可以使用一些树上问题的方法。

本题做法

钦定 $x$ 和 $z$，则此时的方案数为：排除 $x$ 和 $z$ 两个端点后，所有 $x\to z$ 的简单路径上的点的并，也就是经过的所有点双的并。（$y$ 会被经过，当且仅当：对于任意路径，会从 $y$ 所在的点双的某一点进入，同一点双的另一点离开。）

构造广义圆方树后，若给方点赋权 $val$ 为点双大小，圆点赋权 $val=-1$，则答案为圆方树上 $x$ 到 $z$ 路径（含两端点）的权值和。

经过的圆点会被两边的方点各统计一次，应当减掉；端点权值是 $-1$，抵消掉所连方点的自己那一个贡献。完美！

广义圆方树板子：

int dfn[MAXN], low[MAXN], cnt;
int sta[MAXN], top, num;
int val[MAXN], tot;

void tarjan(int x) {
    dfn[x] = low[x] = ++cnt;
    sta[++top] = x;
    val[x] = -1;
    ++tot;
    for (int i = g1.head[x]; i; i = g1.nxt[i]) {
        int y = g1.ver[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
                int u; ++num;
                do {
                    u = sta[top--];
                    g2.add(u, n+num), g2.add(n+num, u);
                    ++val[n+num];
                } while (u != y);
                g2.add(x, n+num), g2.add(n+num, x);
                ++val[n+num];
            }
        } else low[x] = min(low[x], dfn[y]);
    }
}

考虑不枚举 $x$ 和 $z$，枚举 $y$，计算贡献。

只需要计算 $y$ 被不同的路径经过的次数。

因为 $x$ 和 $z$ 只考虑圆点，所以子树中一个圆点的贡献为 $1$，一个方点的贡献应当为 $0$。

然后对于一个 $y$，采用先用当前乘之前的总和，然后把当前累加进总和的方法。

最后当然还要考虑来自父节点的那一部分贡献。

int siz[MAXN]; LL ans;
void solve(int x, int pa) {
    siz[x] = x <= n;
    for (int i = g2.head[x]; i; i = g2.nxt[i]) {
        int y = g2.ver[i];
        if (y == pa) continue;
        solve(y, x);
        ans += 1ll * siz[x] * siz[y] * val[x];
        siz[x] += siz[y];
    }
    ans += 1ll * siz[x] * (tot - siz[x]) * val[x];
}

因为是有序三元组，所以最终答案需要乘 $2$。