題意：給一張 $n$ 點(diǎn) $m$ 邊的簡(jiǎn)單無(wú)向圖，求有多少個(gè)三元組 $(s,c,f)$ ，滿足存在一條從 $s$ 到 $f$ 經(jīng)過(guò) $c$ 的簡(jiǎn)單路徑。

$n\le 10^5,m\le 2\times 10^5$

首先這個(gè) “經(jīng)過(guò) $c$ 的簡(jiǎn)單路徑” ，即 $c$ 取所有 $s$ 到 $f$ 的簡(jiǎn)單路徑的交集，就是能到達(dá)的所有點(diǎn)雙的并集，是圓方樹(shù)的標(biāo)志。具體講解可以參考 PR的博客。

問(wèn)題轉(zhuǎn)換成了：求所有點(diǎn)對(duì)路徑上的點(diǎn)雙的并集的大小 $?2$ （起始點(diǎn)） 之和。

建出圓方樹(shù)，方點(diǎn)權(quán)值為其度數(shù) （即點(diǎn)雙的大小），圓點(diǎn)權(quán)值為 $?1$ （點(diǎn)雙邊界的割點(diǎn)處被統(tǒng)計(jì)了兩次，需要減掉；起始點(diǎn)本來(lái)就要減掉）

這樣統(tǒng)計(jì)所有圓點(diǎn)路徑上的權(quán)值之和，就可以做到 $O(n^2)$

考慮每個(gè)結(jié)點(diǎn)的貢獻(xiàn)，計(jì)算子樹(shù)大小（方點(diǎn)不算大小）瞎算一下就可以 $O(n)$

因?yàn)槲业陌遄颖容^奇怪，需要把邊去重，是 $O(n\log n)$ 的

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <algorithm> #define MAXN 100005 #define MAXM 400005 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } struct edge{int u,v;}e[MAXM]; int head[MAXN],nxt[MAXM],cnt=1; inline void addnode(int u,int v) {e[++cnt]=(edge){u,v};nxt[cnt]=head[u];head[u]=cnt; } int n,m; int dfn[MAXN],low[MAXN],tim; int stk[MAXM],tp,vis[MAXM],bcc[MAXM],vcnt; vector<int> rtt[MAXM]; void tarjan(int u) {dfn[u]=low[u]=++tim;for (int i=head[u];i;i=nxt[i]){if (!vis[i>>1]&&!bcc[i>>1]) vis[(stk[++tp]=i)>>1]=1;if (!dfn[e[i].v]){tarjan(e[i].v);low[u]=min(low[u],low[e[i].v]);if (dfn[u]==low[e[i].v]){rtt[u].push_back(++vcnt);rtt[vcnt].push_back(u);while (vis[i>>1]){int t=stk[tp--];vis[t>>1]=0;rtt[bcc[t>>1]=vcnt].push_back(e[t].v); // rtt[e[t].v].push_back(vcnt);}}}else low[u]=min(low[u],dfn[e[i].v]);} } int val[MAXM],siz[MAXM]; typedef long long ll; ll ans; void dfs(int u,int f,int tot) {siz[u]=(u<=n);vis[u]=1;for (int i=0;i<(int)rtt[u].size();i++){int v=rtt[u][i];if (v!=f){dfs(v,u,tot);ans+=(ll)siz[u]*siz[v]*val[u];siz[u]+=siz[v];}}ans+=(ll)siz[u]*(tot-siz[u])*val[u]; } int main() {n=read(),m=read();for (int i=1;i<=m;i++){int u,v;u=read(),v=read();addnode(u,v),addnode(v,u);}int las=0;vcnt=n;for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i),siz[i]=tim-las,las=tim;for (int i=1;i<=vcnt;i++){sort(rtt[i].begin(),rtt[i].end());rtt[i].erase(unique(rtt[i].begin(),rtt[i].end()),rtt[i].end());}for (int i=1;i<=n;i++) val[i]=-1;for (int i=n+1;i<=vcnt;i++) val[i]=(int)rtt[i].size();for (int i=1;i<=n;i++) if (!vis[i]) dfs(i,0,siz[i]);printf("%lld\n",2*ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【APIO2018】Duathlon 铁人两项 【圆方树】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。