题解 P4630 【[APIO2018] Duathlon 铁人两项】

简单圆方树。 可以发现，答案就是路径上可能经过的点数。考虑将图缩成圆方树，统计树上路径点数。可以简单发现，如果将方点的权值标为点双大小，圆点的权值标为-1，则某条路径上可能经过的点数就是圆方树上路径点权和。直接做是$O(n^2)$的，但是可以改为统计每个点被经过多少次再乘上它的权值，可以利用简单$dfs+dp$做到$O(n)$。 注意图不一定联通。 代码: ```cpp #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) #define For(i,a,b) for(i=(a),i<=(b);++i) #define Forward(i,a,b) for(i=(a),i>=(b);--i) #define Chkmin(a,b) a=a<b?a:b template<typename T>inline void read(T &x) { T f=1;x=0;char c; for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=x*10+(c^48); x*=f; } using namespace std; void file() { #ifndef ONLINE_JUDGE freopen("duathlon.in","r",stdin); freopen("duathlon.out","w",stdout); #endif } const int MAXN=1e6+7,MAXM=2e6+7; static int n,m,Q,e; struct edge { int v,nxt; }; static struct edges { edge p[MAXM]; int head[MAXN]; inline void add(int u,int v) {this->p[++e]=(edge){v,head[u]};this->head[u]=e;} }p,q; static int dfn[MAXN],low[MAXN],bel[MAXN],cnt,sta[MAXN],tp,dfc,w[MAXN],siz; void tarjan(int u,int ff) { dfn[u]=low[u]=++dfc;sta[++tp]=u;w[u]=-1;++siz; for(register int v=p.head[u];v;v=p.p[v].nxt) { if(!dfn[p.p[v].v]) { tarjan(p.p[v].v,u); Chkmin(low[u],low[p.p[v].v]); if(low[p.p[v].v]>=dfn[u]) { q.add(u,++cnt);w[cnt]=1; static int las; do { las=sta[tp--];++w[cnt]; q.add(cnt,las); }while(las^p.p[v].v); } }else if(p.p[v].v^ff)Chkmin(low[u],dfn[p.p[v].v]); } } static int dep[MAXN]; inline void init() { read(n);read(m); static int u,v; Rep(i,1,m)read(u),read(v),p.add(u,v),p.add(v,u); } static int sz[MAXN],vis[MAXN]; static long long ans; void calculate(int u,int ff) { if(u<=n)sz[u]=1,vis[u]=1; long long cnt=0ll; for(register int v=q.head[u];v;v=q.p[v].nxt)if(q.p[v].v^ff) { calculate(q.p[v].v,u); cnt+=(long long)2*sz[u]*sz[q.p[v].v]; sz[u]+=sz[q.p[v].v]; } cnt+=(long long)2*sz[u]*(siz-sz[u]); ans+=cnt*w[u]; } inline void solve() { cnt=n; Rep(i,1,n)if(!vis[i])siz=0,tarjan(i,0),calculate(i,0); printf("%lld\n",ans); } int main() { file(); init(); solve(); return 0; } ```