[APIO2018] Duathlon 铁人两项
teafrogsf
2018-06-26 11:00:40
题意：
给定一个无向图，选择一个三元组$(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$。
```cpp
#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);
}
```