星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

[APIO2018] Duathlon 铁人两项

posted on 2018-06-26 11:00:40 | under 题解 |

题意:
给定一个无向图,选择一个三元组 $(s,c,f)$ ,使得从 $s$ 到 $c$ 到 $f$ 经过的各点只被经过一次,求三元组的方案数, $n\le 10^5,m\le 2\times 10^5$ 。
题解:
考虑枚举点对 $(s,f)$ ,可以发现,在 $s$ 、 $f$ 、 $s\to f$ 的点双里的其他点都可以作为 $c$ 。建立圆方树,方点点权为点双大小,因为割点算重将圆点权值赋为 $-1$ ,正好解决了 $s,f$ 不能选的问题。
问题转变为求 $s,f$ 的树上路径和。暴力枚举是 $O(n^2)$ 的,转换成算每个点的贡献,算一下每个点会被经过多少次即可。勇萌勇这个方法很妙啊,每次dfs之后把前面的子树乘上后面的子树,妙哉。注意一下 $s,f$ 可以反过来,要 $\times 2$ 。

#include<cstdio>
#define neko 200010
#define meko 200010
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
#define travel(i,u,v) for(register int i=head[u],v=e[i].v;i;i=e[i].nex,v=e[i].v)
typedef int arr[neko];
arr dfn,s,low,head,Head;
int n,m;long long ans,nown;
typedef long long arl[neko];
arl siz,tim,val;
struct node
{
    int u,v,nex;
}e[meko<<1],E[meko<<1];
namespace CS_Tree
{
    int t=0,now,cnt,tp=0,dfc=0,las;
    void add(int x,int y)
    {
        E[++t].v=y;
        E[t].u=x;
        E[t].nex=Head[x];
        Head[x]=t;
        E[++t].v=x;
        E[t].u=y;
        E[t].nex=Head[y];
        Head[y]=t;
        val[x]=-1;
    }
    void dfs(int u)
    {
        dfn[u]=low[u]=++dfc;++nown;
        s[++tp]=u;
        for(register int i=head[u],v=e[i].v;i;i=e[i].nex,v=e[i].v)
        {
            if(!dfn[v])
            {
                dfs(v);
                low[u]=chkmin(low[u],low[v]);
                if(dfn[u]<=low[v])
                {
                    ++cnt,now=0;
                    do{add(las=s[tp--],cnt),++now;}while(las^v);
                    add(u,cnt),val[cnt]=++now;
                }
            }
            else low[u]=chkmin(low[u],dfn[v]);
        }
    }
    void debug()
    {f(i,1,t)printf("%d %d %lld %lld\n",E[i].u,E[i].v,val[E[i].u],val[E[i].v]);}
}
namespace solve
{
    int t=0;
    void dfs(int u,int fa)
    {
        if(u<=n)siz[u]=1;
        for(register int i=Head[u],v=E[i].v;i;i=E[i].nex,v=E[i].v)
        {
            if(v^fa)
            {
                dfs(v,u);
                tim[u]+=siz[u]*siz[v]*val[u]*2;
                siz[u]+=siz[v];
            }
        }
        tim[u]+=siz[u]*(nown-siz[u])*val[u]*2;
        ans+=tim[u];
    }
    void add(int x,int y)
    {
        e[++t].v=y;
        e[t].nex=head[x];
        head[x]=t;
    }
}
int main()
{
    int x,y;
    scanf("%d%d",&n,&m);
    f(i,1,m)scanf("%d%d",&x,&y),solve::add(x,y),solve::add(y,x);
    CS_Tree::cnt=n;f(i,1,n)if(!dfn[i])nown=0,CS_Tree::dfs(i),solve::dfs(i,0);
    //f(i,1,n)printf("%d %d\n",dfn[i],low[i]);
    printf("%lld\n",ans);
}