#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10;
vector <int> g[N];
vector <pii> gr[N];
pii val[N], two[N];
ll ans = 0;
int used[N], par[N], vis[N], mx[N], c[N], h[N];
int diam = 0;
vector <int> cyc;
inline bool find_cyc (int v, int p) {
used[v] = 1;
for (auto u : g[v]) {
if (u == p || used[u] == 2) continue;
if (!used[u]) {
par[u] = v;
if (find_cyc(u, v)) return 1;
}
else {
int c = v; cyc.pb(u);
while (c != u) cyc.pb(c), c = par[c];
return 1;
}
}
used[v] = 2; return 0;
}
int mxh, cnt;
inline void calc (int v) {
used[v] = 1; umax(mxh, h[v]);
pii p = {0, 0}, bs = {0, 0};
for (auto u : g[v]) {
if (used[u]) continue;
h[u] = h[v] + 1; calc(u);
map <int, int> mp;
for (auto x : gr[u]) mp[-x.fr] += x.sc;
pii it = *mp.begin(); it.fr = -it.fr; ++it.fr;
gr[v].pb(it);
if (val[u].fr + 1 > p.fr) {
swap(p.fr, p.sc); p.fr = val[u].fr + 1;
bs = val[u]; ++bs.fr;
}
else {
if (val[u].fr + 1 == p.fr) ++bs.sc;
umax(p.sc, val[u].fr + 1);
}
}
val[v] = bs; two[v] = p;
if (!sz(gr[v])) gr[v].pb({0, 1});
umax(diam, p.fr + p.sc);
}
inline void gogo (int v) {
vis[v] = 1; cnt += (h[v] == mxh);
for (auto u : g[v]) if (!vis[u]) gogo(u);
}
inline void dfs (int v) {
used[v] = 1;
if (two[v].fr + two[v].sc == diam) {
if (sz(gr[v]) == 1) ans += gr[v][0].sc;
else {
sort(rall(gr[v]));
if (gr[v][0].fr == gr[v][1].fr) {
ll s = 0;
for (int i = 0; i < sz(gr[v]); ++i) {
if (gr[v][0].fr != gr[v][i].fr) break;
ans += gr[v][i].sc * s;
s += gr[v][i].sc;
}
}
else {
for (int i = 1; i < sz(gr[v]); ++i) {
if (gr[v][1].fr != gr[v][i].fr) break;
ans += gr[v][0].sc * gr[v][i].sc;
}
}
}
}
for (auto u : g[v]) if (!used[u]) dfs(u);
}
inline void solve () {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
int u, v; cin >> u >> v; --u, --v;
g[u].pb(v); g[v].pb(u);
}
find_cyc(0, -1); fill(used, used + N, 0);
for (auto v : cyc) used[v] = vis[v] = 1;
int uk = 1;
for (auto i : cyc) {
mxh = cnt = 0;
calc(i); gogo(i);
mx[uk] = mxh; c[uk] = cnt; ++uk;
}
int half = sz(cyc) / 2;
map <int, ll> mlef, mrig;
multiset <int> slef, srig;
for (int i = 1; i <= sz(cyc); ++i) {
if (sz(srig)) umax(diam, i + mx[i] + *srig.rbegin());
if (sz(slef)) umax(diam, sz(cyc) - i + mx[i] + *slef.rbegin());
srig.insert(mx[i] - i);
if (i >= half + 1) {
slef.insert(mx[i - half] + i - half);
srig.erase(srig.find(mx[i - half] - i + half));
}
}
for (int i = 1; i <= sz(cyc); ++i) {
ans += c[i] * 1ll * (mrig[diam - mx[i] - i] + mlef[diam - sz(cyc) + i - mx[i]]);
mrig[mx[i] - i] += c[i];
if (i >= half + 1) {
mlef[mx[i - half] + i - half] += c[i - half];
mrig[mx[i - half] - i + half] -= c[i - half];
}
if (half * 2 == sz(cyc) && i >= half + 1 && mx[i] + half + mx[i - half] == diam) ans += c[i] * 1ll * c[i - half];
}
fill(used, used + N, 0); for (auto i : cyc) used[i] = 1;
for (auto x : cyc) dfs(x);
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1; //cin >> t;
while (t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11220 KB |
Output is correct |
| 2 |
Correct |
5 ms |
11220 KB |
Output is correct |
| 3 |
Correct |
5 ms |
11220 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11220 KB |
Output is correct |
| 5 |
Correct |
6 ms |
11348 KB |
Output is correct |
| 6 |
Correct |
6 ms |
11348 KB |
Output is correct |
| 7 |
Correct |
5 ms |
11220 KB |
Output is correct |
| 8 |
Correct |
5 ms |
11264 KB |
Output is correct |
| 9 |
Correct |
6 ms |
11264 KB |
Output is correct |
| 10 |
Correct |
8 ms |
11220 KB |
Output is correct |
| 11 |
Correct |
6 ms |
11264 KB |
Output is correct |
| 12 |
Correct |
7 ms |
11264 KB |
Output is correct |
| 13 |
Correct |
7 ms |
11348 KB |
Output is correct |
| 14 |
Correct |
7 ms |
11348 KB |
Output is correct |
| 15 |
Correct |
6 ms |
11348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11604 KB |
Output is correct |
| 2 |
Correct |
6 ms |
11348 KB |
Output is correct |
| 3 |
Correct |
6 ms |
11476 KB |
Output is correct |
| 4 |
Correct |
6 ms |
11348 KB |
Output is correct |
| 5 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 6 |
Correct |
8 ms |
12116 KB |
Output is correct |
| 7 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 8 |
Correct |
9 ms |
12052 KB |
Output is correct |
| 9 |
Correct |
8 ms |
12000 KB |
Output is correct |
| 10 |
Correct |
8 ms |
11900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
23604 KB |
Output is correct |
| 2 |
Correct |
87 ms |
25420 KB |
Output is correct |
| 3 |
Correct |
76 ms |
35136 KB |
Output is correct |
| 4 |
Correct |
64 ms |
24340 KB |
Output is correct |
| 5 |
Correct |
57 ms |
24304 KB |
Output is correct |
| 6 |
Correct |
200 ms |
35280 KB |
Output is correct |
| 7 |
Correct |
135 ms |
31296 KB |
Output is correct |
| 8 |
Correct |
137 ms |
37064 KB |
Output is correct |
| 9 |
Correct |
129 ms |
36828 KB |
Output is correct |
| 10 |
Correct |
104 ms |
40028 KB |
Output is correct |
| 11 |
Correct |
127 ms |
38068 KB |
Output is correct |
| 12 |
Correct |
144 ms |
39468 KB |
Output is correct |
