【APIO2018】铁人两项

题目描述

大意就是给定一张无向图，询问三元组\((s,c,f)\)中满足\(s\neq c\neq f\)且存在\((s\to c\to f)\)的简单路径（每个点最多经过一次）的数量。

\(1\leq n,\leq 10^5,1\leq m\leq 2*10^5\)

我们考虑枚举\(s,f\)然后计算中间\(c\)的数量。我们发现对于一张图上统计两点之间路径上的点数量很好做。于是我们考虑建圆方树。

我们将圆点的权值定为\(-1\)，将方点的权值定为与其直接相连的圆点的数量。\(u\)到\(v\)路径上可能经过的点的数量就是圆方树上\(u\to v\)路径上除了\(u,v\)的点权之和\(-2\)。

于是我们用树形\(\text{DP}\)，计算每个点对答案的贡献。

代码：

#include<bits/stdc++.h>#define ll long long#define N 200005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m;int tot;struct graph { int to[N<<2],nxt[N<<2]; int h[N],cnt; void add(int i,int j) { to[++cnt]=j; nxt[cnt]=h[i]; h[i]=cnt; }}s,g;int dfn[N],low[N],id;int st[N];int val[N];void work(int v,int to) { tot++; g.add(v,tot); val[tot]=1; while(1) { int j=st[st[0]--]; val[tot]++; g.add(tot,j); if(j==to) return ; }}ll tot_size;void tarjan(int v,int fr) { tot_size++; dfn[v]=low[v]=++id; st[++st[0]]=v; for(int i=s.h[v];i;i=s.nxt[i]) { int to=s.to[i]; if(to==fr) continue ; if(!dfn[to]) { tarjan(to,v); low[v]=min(low[v],low[to]); if(low[to]>=dfn[v]) { work(v,to); } } else low[v]=min(low[v],dfn[to]); }}ll ans;int size[N];void dfs(int v) { int tim=0; for(int i=g.h[v];i;i=g.nxt[i]) { int to=g.to[i]; dfs(to); ans+=1ll*val[v]*size[v]*size[to]; tim+=size[v]*size[to]; size[v]+=size[to]; } if(v<=n) size[v]++; if(v<=n) { tim+=(size[v]-1)*(tot_size-size[v]); ans+=1ll*val[v]*(size[v]-1)*(tot_size-size[v]); } else { tim+=size[v]*(tot_size-size[v]); ans+=1ll*val[v]*size[v]*(tot_size-size[v]); }}int main() { n=Get(),m=Get(); tot=n; int a,b; for(int i=1;i<=m;i++) { a=Get(),b=Get(); s.add(a,b),s.add(b,a); } for(int i=1;i<=n;i++) val[i]=-1; for(int i=1;i<=n;i++) { if(dfn[i]) continue ; tot_size=0; tarjan(i,0); dfs(i); ans-=1ll*tot_size*(tot_size-1); } cout<<ans*2; return 0;}