«Программирование в прямом эфире»: как прошел региональный полуфинал ICPC в Университете ИТМО
#undef _GLIBCXX_DEBUG
#include
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector> gs(n);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
x--; y--;
gs[x].insert(y);
gs[y].insert(x);
}
long long ans = 0;
vector weight(n, 1);
set> s;
for (int i = 0; i < n; i++) {
s.emplace(gs[i].size(), i);
}
while (s.size() > 1) {
int i = s.begin()->second;
assert(!gs[i].empty());
if (gs[i].size() > 1) {
break;
}
s.erase(s.begin());
int j = *gs[i].begin();
gs[i].clear();
ans += (long long) 2 * weight[i] * (n - weight[i]);
weight[j] += weight[i];
auto it = gs[j].find(i);
assert(it != gs[j].end());
s.erase({gs[j].size(), j});
gs[j].erase(it);
s.emplace(gs[j].size(), j);
}
if (s.size() == 1) {
cout << ans / 2 << '\n';
return 0;
}
vector> g(n);
for (int i = 0; i < n; i++) {
g[i] = vector(gs[i].begin(), gs[i].end());
}
vector id(n, -1);
int cnt = 0;
for (int i = 0; i < n; i++) {
if ((int) g[i].size() > 2) {
id[i] = cnt++;
}
}
if (cnt == 0) {
for (int i = 0; i < n; i++) {
if ((int) g[i].size() == 2) {
id[i] = cnt++;
break;
}
}
assert(cnt > 0);
}
vector rev_id(n, -1);
for (int i = 0; i < n; i++) {
if (id[i] != -1) {
rev_id[id[i]] = i;
}
}
vector>>> edges(cnt, vector>>(cnt));
for (int i = 0; i < n; i++) {
if (id[i] >= 0) {
for (int j : g[i]) {
if (id[j] >= 0) {
edges[id[i]][id[j]].emplace_back();
}
}
}
}
for (int i = 0; i < n; i++) {
if ((int) g[i].size() == 2 && id[i] == -1) {
vector edge;
edge.push_back(weight[i]);
id[i] = -2;
vector fin(2);
for (int dir = 0; dir < 2; dir++) {
int x = g[i][dir];
int px = i;
while (id[x] == -1) {
assert((int) g[x].size() == 2);
edge.push_back(weight[x]);
id[x] = -2;
int nx = px ^ g[x][0] ^ g[x][1];
px = x;
x = nx;
}
fin[dir] = x;
reverse(edge.begin(), edge.end());
}
edges[id[fin[1]]][id[fin[0]]].push_back(edge);
}
}
vector> dist(cnt, vector(cnt, n + 1));
for (int i = 0; i < cnt; i++) {
dist[i][i] = 0;
}
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < cnt; j++) {
for (auto &p : edges[i][j]) {
dist[i][j] = dist[j][i] = min(dist[i][j], (int) p.size() + 1);
}
}
}
for (int k = 0; k < cnt; k++) {
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < cnt; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
vector>>> edge_pref_sum(cnt, vector>>(cnt));
vector>>> edge_pref_sum_by_pos(cnt, vector>>(cnt));
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < cnt; j++) {
edge_pref_sum[i][j].resize(edges[i][j].size());
edge_pref_sum_by_pos[i][j].resize(edges[i][j].size());
for (int k = 0; k < (int) edges[i][j].size(); k++) {
edge_pref_sum[i][j][k].resize(edges[i][j][k].size() + 1);
edge_pref_sum_by_pos[i][j][k].resize(edges[i][j][k].size() + 1);
for (int t = 0; t < (int) edges[i][j][k].size(); t++) {
edge_pref_sum[i][j][k][t + 1] = edge_pref_sum[i][j][k][t] + edges[i][j][k][t];
edge_pref_sum_by_pos[i][j][k][t + 1] = edge_pref_sum_by_pos[i][j][k][t] + (long long) edges[i][j][k][t] * t;
}
}
}
}
auto get = [&](int i, int j, int k, int from, int to, int coeff_from, int coeff_to) -> long long {
if (from > to) {
return 0;
}
assert(0 <= from && to <= (int) edges[i][j][k].size() - 1);
long long ret = (edge_pref_sum[i][j][k][to + 1] - edge_pref_sum[i][j][k][from]) * coeff_from;
if (coeff_from != coeff_to) {
assert(abs(coeff_from - coeff_to) == to - from);
long long other = edge_pref_sum_by_pos[i][j][k][to + 1] - edge_pref_sum_by_pos[i][j][k][from];
other -= (edge_pref_sum[i][j][k][to + 1] - edge_pref_sum[i][j][k][from]) * from;
ret += other * (coeff_from < coeff_to ? 1 : -1);
}
return ret;
};
for (int v = 0; v < cnt; v++) {
long long w = weight[rev_id[v]];
for (int j = 0; j < cnt; j++) {
ans += dist[v][j] * w * weight[rev_id[j]];
}
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < cnt; j++) {
for (int k = 0; k < (int) edges[i][j].size(); k++) {
int x = dist[v][i];
int y = dist[v][j];
int cc = (y - x + (int) edges[i][j][k].size() + 1) / 2;
cc = min(max(cc, 0), (int) edges[i][j][k].size());
ans += w * get(i, j, k, 0, cc - 1, x + 1, x + cc);
ans += w * get(i, j, k, cc, (int) edges[i][j][k].size() - 1, y + ((int) edges[i][j][k].size() - cc), y + 1);
}
}
}
}
vector> pairs;
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < cnt; j++) {
if (!edges[i][j].empty()) {
pairs.emplace_back(i, j);
}
}
}
for (int ii = 0; ii < cnt; ii++) {
for (int jj = 0; jj < cnt; jj++) {
for (int kk = 0; kk < (int) edges[ii][jj].size(); kk++) {
for (int tt = 0; tt < (int) edges[ii][jj][kk].size(); tt++) {
long long w = edges[ii][jj][kk][tt];
for (int i = 0; i < cnt; i++) {
int d1 = dist[ii][i] + tt + 1;
int d2 = dist[jj][i] + (int) edges[ii][jj][kk].size() - tt;
ans += w * weight[rev_id[i]] * min(d1, d2);
}
for (auto &p : pairs) {
int i = p.first;
int j = p.second;
for (int k = 0; k < (int) edges[i][j].size(); k++) {
if (i == ii && j == jj && k == kk) {
int d1 = tt;
int d2 = (int) edges[ii][jj][kk].size() - tt + dist[i][j] + 1;
if (d1 <= d2) {
ans += w * get(i, j, k, 0, tt, tt, 0);
} else {
int cut = (d1 - d2 + 1) / 2;
ans += w * get(i, j, k, 0, cut - 1, d2, d2 + cut - 1);
ans += w * get(i, j, k, cut, tt, tt - cut, 0);
}
int d3 = (int) edges[ii][jj][kk].size() - 1 - tt;
int d4 = tt + 1 + dist[i][j] + 1;
if (d3 <= d4) {
ans += w * get(i, j, k, tt, (int) edges[i][j][k].size() - 1, 0, (int) edges[i][j][k].size() - 1 - tt);
} else {
int cut = (d3 - d4 + 1) / 2;
ans += w * get(i, j, k, (int) edges[i][j][k].size() - cut, (int) edges[i][j][k].size() - 1, d4 + cut - 1, d4);
ans += w * get(i, j, k, tt, (int) edges[i][j][k].size() - 1 - cut, 0, (int) edges[i][j][k].size() - 1 - cut - tt);
}
} else {
int d1 = dist[ii][i] + tt + 1;
int d2 = dist[jj][i] + (int) edges[ii][jj][kk].size() - tt;
int d3 = dist[ii][j] + tt + 1;
int d4 = dist[jj][j] + (int) edges[ii][jj][kk].size() - tt;
int x = min(d1, d2);
int y = min(d3, d4);
int cc = (y - x + (int) edges[i][j][k].size() + 1) / 2;
cc = min(max(cc, 0), (int) edges[i][j][k].size());
ans += w * get(i, j, k, 0, cc - 1, x + 1, x + cc);
ans += w * get(i, j, k, cc, (int) edges[i][j][k].size() - 1, y + ((int) edges[i][j][k].size() - cc), y + 1);
}
}
}
}
}
}
}
assert(ans % 2 == 0);
cout << ans / 2 << '\n';
return 0;
}
