#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);
map<int, vector<long long>> children;
for (int u : g[v]){
if (u == p || incycle[u]) continue;
pii t = dfs1(u, v, d + 1);
res = combine(res, t);
children[t.first].push_back(t.second);
}
if (!children.empty()){
int da = children.rbegin()->first;
vector<long long> a = children.rbegin()->second;
da -= d;
children.erase(--children.end());
if ((int) a.size() >= 2){
long long sum = accumulate(a.begin(), a.end(), 0LL);
for (long long x : a){
sum -= x;
ans = combine(ans, pii(2 * da, 2 * x * sum));
}
} else if (!children.empty()){
int db = children.rbegin()->first;
vector<long long> b = children.rbegin()->second;
db -= d;
long long sum = accumulate(b.begin(), b.end(), 0LL);
ans = combine(ans, pii(da + db, 2 * a.front() * sum));
}
}
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 |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
308 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 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 |
596 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
2 ms |
596 KB |
Output is correct |
| 8 |
Correct |
2 ms |
596 KB |
Output is correct |
| 9 |
Correct |
2 ms |
596 KB |
Output is correct |
| 10 |
Correct |
3 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
33 ms |
6420 KB |
Output is correct |
| 3 |
Correct |
55 ms |
19732 KB |
Output is correct |
| 4 |
Correct |
29 ms |
6372 KB |
Output is correct |
| 5 |
Correct |
31 ms |
6320 KB |
Output is correct |
| 6 |
Correct |
69 ms |
10828 KB |
Output is correct |
| 7 |
Correct |
48 ms |
8776 KB |
Output is correct |
| 8 |
Correct |
61 ms |
12240 KB |
Output is correct |
| 9 |
Correct |
61 ms |
12316 KB |
Output is correct |
| 10 |
Correct |
62 ms |
13828 KB |
Output is correct |
| 11 |
Correct |
49 ms |
15248 KB |
Output is correct |
| 12 |
Correct |
50 ms |
18456 KB |
Output is correct |
