题面

\(LOJ\)自己找。。

Sol

建立圆方树

考虑枚举起点\(s\)和终点\(t\)
那么答案就是\(s\)到\(t\)间的点双的点数和减去\(s,t\)
设方点权值为点双的点数，圆点的权值为\(-1\)
那么就是求\(s,t\)的路径上的点权和

现在考虑中间的点\(x\)
那么它的贡献就是经过它的路径的条数*它的权值
树\(DP\)得解

# include <bits/stdc++.h> # define IL inline # define RG register # define Fill(a, b) memset(a, b, sizeof(a)) using namespace std; typedef long long ll;IL int Input(){RG int x = 0, z = 1; RG char c = getchar();for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);return x * z; }const int maxn(4e5 + 5);int n, m, dfn[maxn], low[maxn], idx, sum; int sta[maxn], top, tot, val[maxn], size[maxn]; ll ans;struct Edge{int first[maxn], cnt, nxt[maxn << 1], to[maxn << 1];IL void Init(){cnt = 0, Fill(first, -1);}IL void Add(RG int u, RG int v){nxt[cnt] = first[u], to[cnt] = v, first[u] = cnt++;} } e1, e2;IL void Tarjan(RG int u){dfn[u] = low[u] = ++idx, sta[++top] = u, size[u] = 1;for(RG int e = e1.first[u]; e != -1; e = e1.nxt[e]){RG int v = e1.to[e];if(!dfn[v]){Tarjan(v), low[u] = min(low[u], low[v]);if(low[v] >= dfn[u]){RG int x = 0, num = 1; ++tot;do{x = sta[top--], ++num;e2.Add(tot, x), e2.Add(x, tot);size[tot] += size[x];} while(x != v);val[tot] = num, size[u] += size[tot];e2.Add(tot, u), e2.Add(u, tot);}}else low[u] = min(low[u], dfn[v]);} }IL void Dfs(RG int u, RG int ff){RG int tmp = u <= n;ans += 2LL * size[u] * (sum - size[u]) * val[u];for(RG int e = e2.first[u]; e != -1; e = e2.nxt[e]){RG int v = e2.to[e];if(v != ff){ans += 2LL * tmp * size[v] * val[u];tmp += size[v];Dfs(v, u);}} }int main(){e1.Init(), e2.Init();tot = n = Input(), m = Input();for(RG int i = 1; i <= n; ++i) val[i] = -1;for(RG int i = 1; i <= m; ++i){RG int u = Input(), v = Input();e1.Add(u, v), e1.Add(v, u);}for(RG int i = 1; i <= n; ++i)if(!dfn[i]) Tarjan(i), sum = size[i], Dfs(i, 0);printf("%lld\n", ans);return 0; }

转载于:https://www.cnblogs.com/cjoieryl/p/9116019.html

总结

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

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