題目鏈接

洛谷P4630

題解

看了一下部分分，覺得樹的部分很可做，就相當(dāng)于求一個點對路徑長之和的東西，考慮一下能不能轉(zhuǎn)化到一般圖來？
一般圖要轉(zhuǎn)為樹，就使用圓方樹唄

思考一下發(fā)現(xiàn)，兩點之間經(jīng)過的點雙，點雙內(nèi)所有點一定都可以作為中介點
那么我們將方點賦值為點雙大小，為了去重，剩余點賦值\(-1\)
答案就是任意兩點間權(quán)值和之和

我們只需枚舉每個點被經(jīng)過多少次，這就很容易計算了

復(fù)雜度\(O(n)\)

#include<algorithm> #include<iostream> #include<cstdio> #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) #define REP(i,n) for (int i = 1; i <= (n); i++) #define LL long long int using namespace std; const int maxn = 400005,maxm =1000005,INF = 1000000000; inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag; } int hh[maxn],Ne = 1,h[maxn],ne = 1; struct EDGE{int from,to,nxt;}e[maxm],ed[maxm]; inline void build(int u,int v){e[++Ne] = (EDGE){u,v,hh[u]}; hh[u] = Ne;e[++Ne] = (EDGE){v,u,hh[v]}; hh[v] = Ne; } inline void add(int u,int v){ed[++ne] = (EDGE){u,v,h[u]}; h[u] = ne;ed[++ne] = (EDGE){v,u,h[v]}; h[v] = ne; } int n,m,val[maxn],dfn[maxn],low[maxn],inst[maxn],st[maxm],top,cnt,N; void combine(int rt){val[++N] = 1;add(N,rt);while (st[top] != rt && low[st[top]] >= dfn[rt]){inst[st[top]] = false;add(N,st[top--]),val[N]++;} } void dfs(int u,int s){dfn[u] = low[u] = ++cnt; st[++top] = u; inst[u] = true;for (int k = hh[u],to; k; k = e[k].nxt){if (k == s) continue;if (!dfn[to = e[k].to]){dfs(to,k ^ 1);if (low[to] > dfn[u]){top--; val[++N] = 2;add(u,N); add(N,to);}else if (low[to] == dfn[u]) combine(u);low[u] = min(low[u],low[to]);}else if (inst[to]) low[u] = min(low[u],dfn[to]);} } int fa[maxn]; LL siz[maxn],ans,sum; void DFS(int u){siz[u] = u <= n ? 1 : 0;Redge(u) if ((to = ed[k].to) != fa[u]){fa[to] = u,DFS(to),siz[u] += siz[to];}LL tot = u <= n ? sum - 1 : 0;Redge(u) if ((to = ed[k].to) != fa[u]){tot += siz[to] * (sum - siz[to]);}tot += (sum - siz[u]) * siz[u];ans += tot * val[u]; } int main(){N = n = read(); m = read();REP(i,m) build(read(),read());REP(i,n) val[i] = -1;REP(i,n) if (!dfn[i]){sum = cnt; top = 0; dfs(i,-1);sum = cnt - sum; DFS(i);}printf("%lld\n",ans);return 0; }

總結(jié)

1、圓方樹的寫法
2、點雙的寫法
3、一般圖考慮樹的做法的時候，可以考慮建圓方樹

轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/9190204.html

總結(jié)

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

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