【题解】APIO2018 Duathlon 铁人两项

　　首先对于给出的图建立圆方树，然后我们分类讨论每一个点作为中间的中转站出现的情况有多少种，累积到 \(ans\) 中。

　　对于圆点：在任意两个子树内分别选出一个节点都是合法的。

　　对于方点：连接向方点的点均为处于一个双联通分量中的点，彼此之间两两可。所以若我们让这个双联通分量上的一个点作为中转站，在其他任意的两棵子树内挑出两个点来都是合法的。这样乍一看好像是 \(n^{2}\) 的统计方法，我们不妨改变一下：因为答案是累加起来的，我们分别考虑每一棵子树对于答案造成的贡献。这一棵子树中的点可以和另一棵子树内的点任意匹配选出两个，对于不在这两棵子树内的双联通分量上的点均产生有贡献。然后就可以愉快的 \(O(n)\) 统计啦~

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define maxn 500000

int N, n, m, tot, S[maxn], fa[maxn];

int timer, dfn[maxn], low[maxn];

int ans, size[maxn], cnt[maxn];

bool vis[maxn];

struct edge

{

    int cnp = , head[maxn], to[maxn], last[maxn];

    void add(int u, int v)

    {

        if(u == v) return;

        to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++;

        to[cnp] = u, last[cnp] = head[v], head[v] = cnp ++;

    }

}E1, E2, E3;

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void Tarjan(int u)

{

    dfn[u] = low[u] = ++ timer; S[++ S[]] = u;

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

        int v = E1.to[i];

        if(!dfn[v])

        {

            Tarjan(v); low[u] = min(low[u], low[v]);

            if(low[v] >= dfn[u])

            {

                E2.add(++ N, u); cnt[N] ++, cnt[u] ++; int x = ;

                do

                {

                    E2.add(N, x = S[S[] --]); cnt[N] ++, cnt[x] ++;

                }while(x != v);

            }

        }

        else low[u] = min(low[u], dfn[v]);

    }

}

void dfs(int u)

{

    vis[u] = ;

    if(u <= n) size[u] ++;

    for(int i = E2.head[u]; i; i = E2.last[i])

    {

        int v = E2.to[i]; if(v == fa[u]) continue;

        fa[v] = u; dfs(v); size[u] += size[v];

    }

}

void DP(int u)

{

    for(int i = E2.head[u]; i; i = E2.last[i])

    {

        int v = E2.to[i]; if(v == fa[u]) continue;

        DP(v);

    }

    int tem = ;

    if(u <= n)

    {

        for(int i = E2.head[u]; i; i = E2.last[i])

        {

            int v = E2.to[i];

            if(v != fa[u]) tem += (size[v]) * (tot - size[v] - );

            else tem += (tot - size[u]) * (size[u] - );

        }

    }

    else

    {

        if(cnt[u] > )

        {

            for(int i = E2.head[u]; i; i = E2.last[i])

            {

                int v = E2.to[i];

                if(v != fa[u]) tem += (size[v]) * (tot - size[v]) * (cnt[u] - );

                else tem += (tot - size[u]) * (size[u]) * (cnt[u] - );

            }

        }

    }

    ans += tem;

}

signed main()

{

    N = n = read(), m = read();

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

    {

        int u = read(), v = read();

        E1.add(u, v);

    }

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

        if(!dfn[i]) Tarjan(i);

    for(int i = ; i <= N; i ++)

        if(!vis[i])

        {

            dfs(i); tot = size[i];

            DP(i);

        }

    printf("%lld\n", ans);

    return ;

}

巴特西

【题解】APIO2018 Duathlon 铁人两项

最新文章

热门文章