//#define STRESS
#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
#include <chrono>
using namespace std;
using llong = long long;
#ifdef MANSON
#define BUGO(x) cerr << #x << " = " << (x) << '\n';
#define BUGOARR(a) { cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n'; }
#else
#define BUGO(x) ;
#define BUGOARR(a) {}
#endif
using llong = long long;
using uint = unsigned int;
using ullong = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
inline llong rndll(llong l, llong r) { return uniform_int_distribution<llong>(l, r)(rng); }
namespace Brutos
{
pair<int, int> answer(0, 1);
vector<int> nei[200001];
pair<int, int> tx[800000], ty[800000];
template<typename T>
inline T Comb2(T x) { return ((x - (T)1) * x) / (T)2; }
template<class T1, class T2>
ostream& operator<<(ostream& ostr, const pair<T1, T2>& a)
{
return ostr << "{" << a.first << ", " << a.second << "}";
}
void Add(pair<int, int>* a, const pair<int, int>& rhs)
{
if (rhs.first > a->first)
*a = rhs;
else if (rhs.first == a->first)
a->second += rhs.second;
}
namespace Decomp
{
bool used[200001];
bool root[200001];
pair<int, int> ray[200001];
vector<int> line;
int FindCycle(int v, int par)
{
used[v] = true;
for (int to: nei[v])
{
if (to == par) continue;
if (used[to])
{
line.push_back(v);
root[v] = true;
return to;
}
if (int ret = FindCycle(to, v))
{
line.push_back(v);
root[v] = true;
if (v == ret)
return 0;
return ret;
}
}
return 0;
}
void DFS(int v, int par)
{
// cerr << "v: " << v << "\tpar: " << par << endl;
ray[v] = make_pair(0, 1);
for (int to: nei[v])
if (to != par && !root[to])
{
DFS(to, v);
pair<int, int> p = ray[to];
++p.first;
Add(ray + v, p);
}
}
void AddWays(int v, int par)
{
vector<pair<int, int>> chld;
chld.reserve(nei[v].size());
for (int to: nei[v])
if (to != par && !root[to])
{
AddWays(to, v);
chld.push_back({ray[to].first + 1, ray[to].second});
}
if (chld.size() < 2)
return;
sort(chld.begin(), chld.end(), greater<pair<int, int>>());
int i = 2;
while (i < chld.size() && chld[i].first == chld[i - 1].first)
++i;
if (i < chld.size()) chld.erase(chld.begin() + i, chld.end());
/*cerr << "v: " << v << "` chld: ";
for (auto it: chld)
cerr << it << ' ';
cerr << endl;*/
if (chld[0].first == chld[1].first)
{
pair<int, int> cur = {2 * chld[0].first, 0};
int sum = 0;
for (const pair<int, int>& p: chld)
{
cur.second -= Comb2(p.second);
// if (v == 1)
// cerr << "delta -" << Comb2(p.second) << endl;
sum += p.second;
}
cur.second += Comb2(sum);
// if (v == 1)
// cerr << "v: 1, cur: " << cur << endl;
Add(&answer, cur);
}
else
{
int sum = 0;
for (int i = 1; i < chld.size(); ++i)
sum += chld[i].second;
pair<int, int> cur = {chld[0].first + chld[1].first, chld[0].second * sum};
Add(&answer, cur);
}
}
void Decompose(vector<pair<int, int>>* res)
{
FindCycle(1, -1);
#ifdef DEBUG
cerr << line.size() << endl;
for (int v: line)
cerr << v << ' ';
cerr << '\n';
#endif
res->resize(line.size());
for (int i = 0; i < line.size(); ++i)
{
DFS(line[i], -1);
AddWays(line[i], -1);
(*res)[i] = ray[line[i]];
#ifdef DEBUG
cerr << line[i] << ": " << (*res)[i] << '\n';
#endif
}
}
};
void Build(pair<int, int>* t, int v, int vl, int vr, const vector<pair<int, int>>& a)
{
if (vl == vr)
{
t[v] = a[vr];
return;
}
int vm = (vl + vr) / 2;
Build(t, v * 2, vl, vm, a);
Build(t, v * 2 + 1, vm + 1, vr, a);
t[v] = t[v * 2];
Add(t + v, t[v * 2 + 1]);
}
pair<int, int> Max(pair<int, int>* t, int v, int vl, int vr, int l, int r)
{
if (vl == l && vr == r)
return t[v];
int vm = (vl + vr) / 2;
if (r <= vm)
return Max(t, v * 2, vl, vm, l, r);
else if (l > vm)
return Max(t, v * 2 + 1, vm + 1, vr, l, r);
pair<int, int> res = Max(t, v * 2, vl, vm, l, vm);
Add(&res, Max(t, v * 2 + 1, vm + 1, vr, vm + 1, r));
return res;
}
#ifdef ALL_LL
#undef int
#endif // ALL_LL
int Solve(int nodes, const vector<pair<int, int>>& edges)
#ifdef ALL_LL
#define int llong
#endif // ALL_LL
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for (auto [u, v]: edges)
{
nei[u].push_back(v);
nei[v].push_back(u);
}
vector<pair<int, int>> a;
Decomp::Decompose(&a);
int n = a.size();
vector<pair<int, int>> x(n), y(n);
for (int i = 0; i < n; ++i)
{
x[i] = {i + a[i].first, a[i].second};
y[i] = {n - i + a[i].first, a[i].second};
#ifdef DEBUG
cerr << "i: " << i << ": x = " << x[i] << " y = " << y[i] << " a[i] = " << a[i] << endl;
#endif
}
Build(tx, 1, 0, n - 1, x);
Build(ty, 1, 0, n - 1, y);
for (int l = 0; l + 1 < n; ++l)
{
int s = l + 1;
int e = l + n / 2;
e = min(e, n - 1);
if (s <= e)
{
pair<int, int> mx = Max(tx, 1, 0, n - 1, s, e);
Add(&answer, {mx.first - l + a[l].first, mx.second * a[l].second});
}
s = l + (n + 1) / 2;
e = n - 1;
if (s <= e)
{
pair<int, int> mx = Max(ty, 1, 0, n - 1, s, e);
Add(&answer, {mx.first + l + a[l].first, mx.second * a[l].second});
}
}
// cerr << answer.first<< ' ';
return answer.second;
}
/*
19
6 2
6 4
1 4
1 5
2 3
6 7
7 8
7 9
6 10
10 11
11 12
8 13
9 14
3 15
10 16
16 17
16 18
2 19
4 19
6
6 2
6 4
1 4
1 5
2 3
2 4
*/
}
const int N = 200'002;
int c[N], used[N];
vector<int> g[N], h;
struct el {
int l;
llong q;
}mx1[N], mx2[N], dp[N];
vector<el> a;
el operator+(const el& a, const el& b) {
return { a.l,a.q + b.q };
}
bool operator<(const el& a, const el& b) {
if (a.l == b.l)
return a.q < b.q;
return a.l < b.l;
}
int Dfs(int v, int p)
{
used[v] = 1;
for(int to: g[v])
if (to != p) {
if (used[to]) {
c[v] = 1;
h.push_back(v);
return to;
}
int x = Dfs(to, v);
if (x != 0) {
c[v] = 1;
h.push_back(v);
return (x == v) ? 0 : x;
}
}
return 0;
}
void DfsDp(int v, int p) {
for (int to : g[v])
if (to != p && c[to] != 1) {
DfsDp(to, v);
el x = { mx1[to].l + 1, mx1[to].q };
if (x.l > mx1[v].l) {
mx2[v] = mx1[v];
mx1[v] = x;
}
else if (x.l == mx1[v].l)
mx1[v].q += x.q;
else if (x.l > mx2[v].l)
mx2[v] = x;
else if (x.l == mx2[v].l)
mx2[v].q += x.q;
if (dp[v].l == dp[to].l)
dp[v] = dp[v] + dp[to];
if (dp[v].l < dp[to].l)
dp[v] = dp[to];
}
if (!mx1[v].l)
mx1[v] = {0, 1};
if (!mx2[v].l)
mx2[v] = {0, 1};
if (v == 4&&0)
{
cerr << "v = 4\n";
cerr << mx1[v].l << ' ' << mx1[v].q << '\n';
cerr << mx2[v].l << ' ' << mx2[v].q << '\n';
}
el x;
llong sum = 0;
for (int to : g[v])
if (to != p && c[to] != 1)
if (mx1[to].l + 1 == mx1[v].l)
sum += (mx1[v].q - mx1[to].q) * mx1[to].q;
sum /= 2;
if (v == 1&&0)
cerr << "sum: " << sum << '\n';
x = { sum ? el{2 * mx1[v].l, sum} : el{mx1[v].l + mx2[v].l, mx1[v].q * mx2[v].q} };
if (x.l == dp[v].l && x.l != 0)
dp[v].q += x.q;
dp[v] = max(dp[v], x);
if (!dp[v].l)
dp[v] = {0, 1};
}
el t[4 * N];
void Build(int v, int vl, int vr)
{
if (vl == vr)
{
t[v] = {a[vl].l, a[vl].q};
return;
}
int m = (vl + vr) / 2;
Build(v * 2, vl, m);
Build(v * 2 + 1, m + 1, vr);
if (t[v * 2].l == t[v * 2 + 1].l)
{
t[v].l = t[v * 2].l;
t[v].q = t[v * 2].q + t[v * 2 + 1].q;
}
else t[v] = max(t[v * 2], t[v * 2 + 1]);
}
el GetMax(int v, int vl, int vr, int l, int r)
{
if (vl == l && vr == r)
return t[v];
int m = (vl + vr) / 2;
el r1, r2;
if (r <= m)
return GetMax(v * 2, vl, m, l, r);
if (l > m)
return GetMax(v * 2 + 1, m + 1, vr, l, r);
r1 = GetMax(v * 2, vl, m, l, m);
r2 = GetMax(v * 2 + 1, m + 1, vr, m + 1, r);
if (r1.l == r2.l)
return {r1.l, r1.q + r2.q};
return max(r1, r2);
}
int main()
{
int n;
#ifdef STRESS
n = 15;
vector<pair<int, int>> edges;
for (int v = 2; v <= n; ++v)
{
int u = rnd(1, v - 1);
cout << u << ' ' << v << '\n';
edges.push_back({u, v});
g[u].push_back(v);
g[v].push_back(u);
}
do {
int v = rnd(1, n);
int u = rnd(1, n);
if (u == v || count(edges.begin(), edges.end(), pair{u, v}) || count(edges.begin(), edges.end(), pair{v, u})) continue;
edges.push_back({u, v});
g[u].push_back(v);
g[v].push_back(u);
cout << u << ' ' << v << '\n';
break;
} while (true);
cout << "Brutos: " << Brutos::Solve(n, edges) << endl;
#else
cin >> n;
for (int i = 0; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
#endif
Dfs(1, -1);
el ans = { 0,1 };
for (int i = 1; i <= n; i++) {
if (c[i]) {
DfsDp(i, -1);
if (dp[i].l == ans.l)
ans.q += dp[i].q;
else
ans = max(ans, dp[i]);
}
//cerr << "dp" << i << ' ' << dp[i].l << ' ' << dp[i].q << '\n';
//cerr << "ans " << ans.l << ' ' << ans.q << '\n';
}
for (int i = 1; i <= n; i++);
for (int v : h) {
// cerr << v << ' ';
a.push_back(mx1[v]);
}
//cerr << '\n';
for (int v : h) {
//cerr << mx1[v].l << ' ';
a.push_back(mx1[v]);
}
//cerr << '\n';
//for (auto v : a)
//cerr << v.l << ' ';
//cerr << '\n';
n = (int)a.size() / 2;
for (int i = 0; i < a.size(); i++) {
a[i].l += i;
// cerr << a[i].l << ' ' << a[i].q << '\n';
//if (a[i].q == 0)a[i].q++;
}
//cerr << '\n';
Build(1, 0, (int)a.size() - 1);
//cerr << "ans " << ans.l << ' ' << ans.q << '\n';
for (int i = 0; i < n; i++) {
el cur = GetMax(1, 0, 2 * n - 1, i + 1, i + n / 2);
//cerr << i + 1 << "..." << i + n / 2 << "..." << cur.l << ' ' << cur.q << '\n';
cur.l -= 2 * i;
cur.l += a[i].l;
cur.q *= a[i].q;
//cerr << i + 1 << "..." << i + n / 2 << "..." << cur.l << ' ' << cur.q << "\n\n";
if (cur.l == ans.l)
ans.q += cur.q;
else
ans = max(ans, cur);
}
cout << ans.q << '\n';
return 0;
}
Compilation message
shymbulak.cpp: In function 'void Brutos::Decomp::AddWays(int, int)':
shymbulak.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | while (i < chld.size() && chld[i].first == chld[i - 1].first)
| ~~^~~~~~~~~~~~~
shymbulak.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if (i < chld.size()) chld.erase(chld.begin() + i, chld.end());
| ~~^~~~~~~~~~~~~
shymbulak.cpp:126:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int i = 1; i < chld.size(); ++i)
| ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void Brutos::Decomp::Decompose(std::vector<std::pair<int, int> >*)':
shymbulak.cpp:142:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int i = 0; i < line.size(); ++i)
| ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void DfsDp(int, int)':
shymbulak.cpp:333:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
333 | if (v == 1&&0)
| ^~
shymbulak.cpp:335:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
335 | x = { sum ? el{2 * mx1[v].l, sum} : el{mx1[v].l + mx2[v].l, mx1[v].q * mx2[v].q} };
| ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:423:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
423 | for (int i = 1; i <= n; i++);
| ^~~
shymbulak.cpp:424:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
424 | for (int v : h) {
| ^~~
shymbulak.cpp:438:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<el>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
438 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9708 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 4 |
Correct |
8 ms |
9708 KB |
Output is correct |
| 5 |
Correct |
8 ms |
9708 KB |
Output is correct |
| 6 |
Correct |
6 ms |
9708 KB |
Output is correct |
| 7 |
Correct |
6 ms |
9708 KB |
Output is correct |
| 8 |
Correct |
6 ms |
9708 KB |
Output is correct |
| 9 |
Correct |
6 ms |
9708 KB |
Output is correct |
| 10 |
Correct |
6 ms |
9708 KB |
Output is correct |
| 11 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 12 |
Correct |
6 ms |
9708 KB |
Output is correct |
| 13 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 14 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 15 |
Correct |
7 ms |
9836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9964 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
8 ms |
9964 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 5 |
Correct |
10 ms |
10220 KB |
Output is correct |
| 6 |
Correct |
10 ms |
10240 KB |
Output is correct |
| 7 |
Correct |
10 ms |
10220 KB |
Output is correct |
| 8 |
Correct |
10 ms |
10220 KB |
Output is correct |
| 9 |
Correct |
10 ms |
10348 KB |
Output is correct |
| 10 |
Correct |
10 ms |
10220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
17792 KB |
Output is correct |
| 2 |
Correct |
117 ms |
18284 KB |
Output is correct |
| 3 |
Correct |
101 ms |
27488 KB |
Output is correct |
| 4 |
Correct |
94 ms |
18540 KB |
Output is correct |
| 5 |
Correct |
89 ms |
18412 KB |
Output is correct |
| 6 |
Correct |
234 ms |
24556 KB |
Output is correct |
| 7 |
Correct |
196 ms |
21868 KB |
Output is correct |
| 8 |
Correct |
175 ms |
26860 KB |
Output is correct |
| 9 |
Correct |
179 ms |
26348 KB |
Output is correct |
| 10 |
Correct |
184 ms |
28684 KB |
Output is correct |
| 11 |
Correct |
231 ms |
26080 KB |
Output is correct |
| 12 |
Correct |
207 ms |
29408 KB |
Output is correct |
