题目链接：

[APIO2018]铁人两项

对于点双连通分量有一个性质：在同一个点双里的三个点$a,b,c$，一定存在一条从$a$到$c$的路径经过$b$且经过的点只被经过一次。

那么我们建出原图的圆方树，枚举中间点$b$，一对合法的$a,c$需要使这两个点位于与$b$直接相连的方点的不同子树中。树形$DP$，对圆点和方点分别统计答案即可。

#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int n,m; int x,y; vector<int>q[200010]; int head[100010]; int to[400010]; int next[400010]; int size[200010]; int low[100010]; int dfn[100010]; int tot; int cnt; int num; int st[100010]; int top; int vis[200010]; ll ans; int sum; void add(int x,int y) {tot++;next[tot]=head[x];head[x]=tot;to[tot]=y; } void insert(int x,int y) {q[x].push_back(y); } void tarjan(int x) {st[++top]=x;low[x]=dfn[x]=++num;for(int i=head[x];i;i=next[i]){if(!dfn[to[i]]){tarjan(to[i]);low[x]=min(low[x],low[to[i]]);if(low[to[i]]>=dfn[x]){insert(++cnt,x);insert(x,cnt);int now=0;do{now=st[top--];insert(cnt,now);insert(now,cnt);}while(now!=to[i]);}}else{low[x]=min(low[x],dfn[to[i]]);}} } void dfs(int x,int fa) {vis[x]=1;size[x]=(x<=n?1:0);int len=q[x].size();for(int i=0;i<len;i++){int to=q[x][i];if(to!=fa){dfs(to,x);size[x]+=size[to];}} } void tree_dp(int x,int fa) {int len=q[x].size();for(int i=0;i<len;i++){int to=q[x][i];if(to!=fa){tree_dp(to,x);}}if(x<=n){for(int i=0;i<len;i++){int to=q[x][i];if(to!=fa){ans+=1ll*size[to]*(sum-size[to]-1);}else{ans+=1ll*(sum-size[x])*(size[x]-1);}}}else if(len>=3){for(int i=0;i<len;i++){int to=q[x][i];if(to!=fa){ans+=1ll*size[to]*(sum-size[to])*(len-2);}else{ans+=1ll*(sum-size[x])*size[x]*(len-2);}}} } int main() {scanf("%d%d",&n,&m);cnt=n;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}for(int i=1;i<=n;i++){if(!dfn[i]){tarjan(i);}}for(int i=1;i<=cnt;i++){if(!vis[i]){dfs(i,0);sum=size[i];tree_dp(i,0);}}printf("%lld",ans); }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10346332.html

总结

以上是生活随笔为你收集整理的[APIO2018]铁人两项——圆方树+树形DP的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。