#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> color;
vector<int> cycle;
stack<int> st;
bool dfs0(int v, int p){
st.push(v);
color[v] = 1;
for (int u : g[v]){
if (u == p) continue;
if (color[u] == 0){
if (dfs0(u, v)) return true;
}
if (color[u] == 1){
while (!st.empty()){
int x = st.top();
st.pop();
cycle.push_back(x);
if (x == u) break;
}
return true;
}
}
color[v] = 2;
st.pop();
return false;
}
vector<bool> incycle;
#define pii pair<int, long long>
const pii inf(-1e9, 0);
pii combine(const pii &x, const pii &y){
if (x.first > y.first) return x;
if (x.first < y.first) return y;
return pii(x.first, x.second + y.second);
}
pii ans = inf;
pii dfs1(int v, int p, int d){
pii res(d, 1);
vector<pii> children;
for (int u : g[v]){
if (u == p || incycle[u]) continue;
pii t = dfs1(u, v, d + 1);
res = combine(res, t);
children.push_back(t);
}
int sz = (int) children.size();
for (int i = 0; i < sz; i++){
for (int j = i + 1; j < sz; j++){
auto x = children[i], y = children[j];
pii t;
t.first = x.first + y.first - 2 * d;
t.second = 2 * x.second * y.second;
ans = combine(ans, t);
}
}
return res;
}
struct SegmentTree{
int n;
vector<pii> tree;
void build(int v, int tl, int tr, const vector<pii> &a){
if (tl == tr){
tree[v] = a[tl];
} else {
int tm = (tl + tr) >> 1;
build(v << 1, tl, tm, a);
build(v << 1 | 1, tm + 1, tr, a);
tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
}
}
SegmentTree(const vector<pii> &a){
n = (int) a.size();
tree.assign(4 * n + 5, inf);
build(1, 0, n - 1, a);
}
pii get(int v, int tl, int tr, int l, int r){
if (l <= tl && tr <= r) return tree[v];
if (tl > r || tr < l) return inf;
int tm = (tl + tr) >> 1;
return combine(get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
}
pii get(int l, int r){
return get(1, 0, n - 1, l, r);
}
};
int main(){
ios_base::sync_with_stdio(false);
int n;
cin >> n;
g.resize(n);
for (int i = 0; i < n; i++){
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
color.assign(n, 0);
dfs0(0, 0);
int k = (int) cycle.size();
assert(k >= 3);
incycle.assign(n, false);
for (int v : cycle) incycle[v] = true;
vector<int> a(k), b(k);
vector<pii> pos(k), neg(k);
for (int i = 0; i < k; i++){
int v = cycle[i];
pii t = dfs1(v, -1, 0);
a[i] = t.first;
b[i] = t.second;
pos[i] = pii(i + a[i], b[i]);
neg[i] = pii(-i + a[i], b[i]);
}
SegmentTree st_pos(pos);
SegmentTree st_neg(neg);
int h = k / 2;
for (int i = 0; i < k; i++){ // case one
int tl = (i + 1) % k, tr = (i + h) % k;
vector<pair<int, int>> seg;
if (tl <= tr){
seg.emplace_back(tl, tr);
} else {
seg.emplace_back(tl, n - 1);
seg.emplace_back(0, tr);
}
for (auto [l, r] : seg){
pii t = st_pos.get(l, r);
if (l > i){ // i .. l .. r
t.first += -i + a[i];
} else { // l .. r .. i
t.first += k - i + a[i];
}
t.second *= b[i];
ans = combine(ans, t);
}
}
for (int i = 0; i < k; i++){ // case two
int tl = (i - h + k) % k, tr = (i - 1 + k) % k;
vector<pair<int, int>> seg;
if (tl <= tr){
seg.emplace_back(tl, tr);
} else {
seg.emplace_back(tl, n - 1);
seg.emplace_back(0, tr);
}
for (auto [l, r] : seg){
pii t = st_neg.get(l, r);
if (r < i){ // l .. r .. i
t.first += i + a[i];
} else { // i .. l .. r
t.first += k + i + a[i];
}
t.second *= b[i];
ans = combine(ans, t);
}
}
cout << ans.second / 2 << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
320 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
648 KB |
Output is correct |
| 6 |
Correct |
33 ms |
852 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
3 ms |
596 KB |
Output is correct |
| 9 |
Correct |
2 ms |
592 KB |
Output is correct |
| 10 |
Correct |
2 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
5824 KB |
Output is correct |
| 2 |
Correct |
49 ms |
6572 KB |
Output is correct |
| 3 |
Correct |
70 ms |
20800 KB |
Output is correct |
| 4 |
Correct |
25 ms |
7500 KB |
Output is correct |
| 5 |
Correct |
28 ms |
7376 KB |
Output is correct |
| 6 |
Correct |
65 ms |
13140 KB |
Output is correct |
| 7 |
Correct |
67 ms |
10608 KB |
Output is correct |
| 8 |
Correct |
56 ms |
14668 KB |
Output is correct |
| 9 |
Correct |
56 ms |
14764 KB |
Output is correct |
| 10 |
Correct |
59 ms |
16284 KB |
Output is correct |
| 11 |
Execution timed out |
1571 ms |
18708 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
