[BZOJ5463][APIO2018]铁人两项(圆方树DP)

题意：给出一张图，求满足存在一条从u到v的长度大于3的简单路径的有序点对(u,v)个数。

做了上一题[HDU5739]Fantasia(点双连通分量+DP)，这个题就是一个NOIP题了。

一开始考虑了各种各样的情况，最后发现几乎没有什么特殊情况，程序很优美。

首先和上一题一样建出圆方树，然后如果选择了点对(a,c)，那么b一定在树上a到c的路径上。

给树上每个BCC点权为这个BCC的大小，普通点点权设为-1，那么答案就是所有起点终点均为普通点的路径的权值和。直接树形DP即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 const int N=200010;
 9 ll ans;
10 int n,m,u,v,bcc,tim,top,S,sz[N],dfn[N],low[N],stk[N],val[N];
11 
12 struct E{
13     int cnt,h[N],nxt[N<<1],to[N<<1];
14     void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
15 
16     void dfs(int x){
17         ans+=2ll*val[x]*(S-sz[x])*(sz[x]-(x<=n));
18         if (x<=n) ans+=2ll*val[x]*(S-1);
19         for (int i=h[x],k; i; i=nxt[i])
20                 dfs(k=to[i]),ans+=1ll*val[x]*(sz[x]-sz[k]-(x<=n))*sz[k];
21     }
22 }G,G1;
23 
24 void tarjan(int x,int fa){
25     dfn[x]=low[x]=++tim; stk[++top]=x;
26     sz[x]=1; val[x]=-1;
27     for (int i=G.h[x],k; i; i=G.nxt[i])
28         if ((k=G.to[i])!=fa){
29             if (dfn[k]) low[x]=min(low[x],dfn[k]);
30             else{
31                 tarjan(k,x); low[x]=min(low[x],low[k]);
32                 if (low[k]>=dfn[x]){
33                     bcc++; int t; G1.add(x,bcc);
34                     do{
35                         t=stk[top--]; val[bcc]++; G1.add(bcc,t); sz[bcc]+=sz[t];
36                     }while (t!=k);
37                     val[bcc]++; sz[x]+=sz[bcc];
38                 }
39             }
40         }
41 }
42 
43 int main(){
44     freopen("c.in","r",stdin);
45     freopen("c.out","w",stdout);
46     scanf("%d%d",&n,&m); bcc=n;
47     rep(i,1,m) scanf("%d%d",&u,&v),G.add(u,v),G.add(v,u);
48     rep(i,1,n) if (!dfn[i]) tarjan(i,0),S=sz[i],G1.dfs(i);
49     printf("%lld
",ans);
50     return 0;
51 }