#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200'002;
int c[N], used[N];
vector<int> g[N], h;
struct el {
int l;
llong q;
}ray[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) {
el s;
dp[v] = s = { -1,-1 };
ray[v] = { 0,1 };
for (int to : g[v])
if (to != p && c[to] != 1) {
DfsDp(to, v);
//el x = Check(ray[to]);
el x = { ray[to].l + 1, ray[to].q };
if (x.l > ray[v].l) {
s = ray[v];
ray[v] = x;
}
else if (x.l == ray[v].l)
ray[v].q += x.q;
else if (x.l > s.l)
s = x;
else if (x.l == s.l)
s.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 (s.l != -1) {
el x = { ray[v].l + s.l, ray[v].q * s.q };
if (x.l == dp[v].l)
dp[v].q += x.q;
dp[v] = max(dp[v], x);
}
el x;
llong sum = 0;
for (int to : g[v])
if (to != p && c[to] != 1)
if (ray[to].l + 1 == ray[v].l)
sum += (ray[v].q - ray[to].q) * ray[to].q;
sum /= 2;
if (sum)x = { 2 * ray[v].l,sum };
else x = ray[v];
if (x.l == dp[v].l)
dp[v].q += x.q;
dp[v] = max(dp[v], x);
}
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;
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);
}
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.l != 0)
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 v : h) {
// cerr << v << ' ';
a.push_back(ray[v]);
}
//cerr << '\n';
for (int v : h) {
//cerr << mx1[v].l << ' ';
a.push_back(ray[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.l != 0)
ans.q += cur.q;
else ans = max(ans, cur);
}
cout << ans.q << '\n';
return 0;
}
Compilation message
shymbulak.cpp:11:5: error: 'llong' does not name a type; did you mean 'ulong'?
11 | llong q;
| ^~~~~
| ulong
shymbulak.cpp: In function 'el operator+(const el&, const el&)':
shymbulak.cpp:15:17: error: 'const struct el' has no member named 'q'
15 | return { a.l,a.q + b.q };
| ^
shymbulak.cpp:15:23: error: 'const struct el' has no member named 'q'
15 | return { a.l,a.q + b.q };
| ^
shymbulak.cpp:15:25: error: could not convert '{a.el::l, <expression error>}' from '<brace-enclosed initializer list>' to 'el'
15 | return { a.l,a.q + b.q };
| ^
| |
| <brace-enclosed initializer list>
shymbulak.cpp: In function 'bool operator<(const el&, const el&)':
shymbulak.cpp:19:12: error: 'const struct el' has no member named 'q'
19 | return a.q < b.q;
| ^
shymbulak.cpp:19:18: error: 'const struct el' has no member named 'q'
19 | return a.q < b.q;
| ^
shymbulak.cpp: In function 'void DfsDp(int, int)':
shymbulak.cpp:42:22: error: no match for 'operator=' (operand types are 'el' and '<brace-enclosed initializer list>')
42 | dp[v] = s = { -1,-1 };
| ^
shymbulak.cpp:9:8: note: candidate: 'constexpr el& el::operator=(const el&)'
9 | struct el {
| ^~
shymbulak.cpp:9:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const el&'
shymbulak.cpp:9:8: note: candidate: 'constexpr el& el::operator=(el&&)'
shymbulak.cpp:9:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'el&&'
shymbulak.cpp:43:17: error: no match for 'operator=' (operand types are 'el' and '<brace-enclosed initializer list>')
43 | ray[v] = { 0,1 };
| ^
shymbulak.cpp:9:8: note: candidate: 'constexpr el& el::operator=(const el&)'
9 | struct el {
| ^~
shymbulak.cpp:9:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const el&'
shymbulak.cpp:9:8: note: candidate: 'constexpr el& el::operator=(el&&)'
shymbulak.cpp:9:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'el&&'
shymbulak.cpp:48:36: error: 'struct el' has no member named 'q'
48 | el x = { ray[to].l + 1, ray[to].q };
| ^
shymbulak.cpp:48:38: error: too many initializers for 'el'
48 | el x = { ray[to].l + 1, ray[to].q };
| ^
shymbulak.cpp:54:12: error: 'struct el' has no member named 'q'
54 | ray[v].q += x.q;
| ^
shymbulak.cpp:54:19: error: 'struct el' has no member named 'q'
54 | ray[v].q += x.q;
| ^
shymbulak.cpp:58:7: error: 'struct el' has no member named 'q'
58 | s.q += x.q;
| ^
shymbulak.cpp:58:14: error: 'struct el' has no member named 'q'
58 | s.q += x.q;
| ^
shymbulak.cpp:65:35: error: 'struct el' has no member named 'q'
65 | el x = { ray[v].l + s.l, ray[v].q * s.q };
| ^
shymbulak.cpp:65:41: error: 'struct el' has no member named 'q'
65 | el x = { ray[v].l + s.l, ray[v].q * s.q };
| ^
shymbulak.cpp:65:43: error: too many initializers for 'el'
65 | el x = { ray[v].l + s.l, ray[v].q * s.q };
| ^
shymbulak.cpp:67:10: error: 'struct el' has no member named 'q'
67 | dp[v].q += x.q;
| ^
shymbulak.cpp:67:17: error: 'struct el' has no member named 'q'
67 | dp[v].q += x.q;
| ^
shymbulak.cpp:71:2: error: 'llong' was not declared in this scope; did you mean 'ulong'?
71 | llong sum = 0;
| ^~~~~
| ulong
shymbulak.cpp:75:5: error: 'sum' was not declared in this scope
75 | sum += (ray[v].q - ray[to].q) * ray[to].q;
| ^~~
shymbulak.cpp:75:20: error: 'struct el' has no member named 'q'
75 | sum += (ray[v].q - ray[to].q) * ray[to].q;
| ^
shymbulak.cpp:75:32: error: 'struct el' has no member named 'q'
75 | sum += (ray[v].q - ray[to].q) * ray[to].q;
| ^
shymbulak.cpp:75:45: error: 'struct el' has no member named 'q'
75 | sum += (ray[v].q - ray[to].q) * ray[to].q;
| ^
shymbulak.cpp:76:2: error: 'sum' was not declared in this scope
76 | sum /= 2;
| ^~~
shymbulak.cpp:77:33: error: no match for 'operator=' (operand types are 'el' and '<brace-enclosed initializer list>')
77 | if (sum)x = { 2 * ray[v].l,sum };
| ^
shymbulak.cpp:9:8: note: candidate: 'constexpr el& el::operator=(const el&)'
9 | struct el {
| ^~
shymbulak.cpp:9:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const el&'
shymbulak.cpp:9:8: note: candidate: 'constexpr el& el::operator=(el&&)'
shymbulak.cpp:9:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'el&&'
shymbulak.cpp:80:9: error: 'struct el' has no member named 'q'
80 | dp[v].q += x.q;
| ^
shymbulak.cpp:80:16: error: 'struct el' has no member named 'q'
80 | dp[v].q += x.q;
| ^
shymbulak.cpp: In function 'void Build(int, int, int)':
shymbulak.cpp:88:26: error: '__gnu_cxx::__alloc_traits<std::allocator<el>, el>::value_type' {aka 'struct el'} has no member named 'q'
88 | t[v] = { a[vl].l,a[vl].q };
| ^
shymbulak.cpp:88:28: error: no match for 'operator=' (operand types are 'el' and '<brace-enclosed initializer list>')
88 | t[v] = { a[vl].l,a[vl].q };
| ^
shymbulak.cpp:9:8: note: candidate: 'constexpr el& el::operator=(const el&)'
9 | struct el {
| ^~
shymbulak.cpp:9:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const el&'
shymbulak.cpp:9:8: note: candidate: 'constexpr el& el::operator=(el&&)'
shymbulak.cpp:9:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'el&&'
shymbulak.cpp:97:8: error: 'struct el' has no member named 'q'
97 | t[v].q = t[v * 2].q + t[v * 2 + 1].q;
| ^
shymbulak.cpp:97:21: error: 'struct el' has no member named 'q'
97 | t[v].q = t[v * 2].q + t[v * 2 + 1].q;
| ^
shymbulak.cpp:97:38: error: 'struct el' has no member named 'q'
97 | t[v].q = t[v * 2].q + t[v * 2 + 1].q;
| ^
shymbulak.cpp: In function 'el GetMax(int, int, int, int, int)':
shymbulak.cpp:114:20: error: 'struct el' has no member named 'q'
114 | return { r1.l,r1.q + r2.q };
| ^
shymbulak.cpp:114:27: error: 'struct el' has no member named 'q'
114 | return { r1.l,r1.q + r2.q };
| ^
shymbulak.cpp:114:29: error: could not convert '{r1.el::l, <expression error>}' from '<brace-enclosed initializer list>' to 'el'
114 | return { r1.l,r1.q + r2.q };
| ^
| |
| <brace-enclosed initializer list>
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:128:17: error: too many initializers for 'el'
128 | el ans = { 0,1 };
| ^
shymbulak.cpp:133:9: error: 'struct el' has no member named 'q'
133 | ans.q += dp[i].q;
| ^
shymbulak.cpp:133:20: error: 'struct el' has no member named 'q'
133 | ans.q += dp[i].q;
| ^
shymbulak.cpp:153:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<el>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
shymbulak.cpp:166:7: error: 'struct el' has no member named 'q'
166 | cur.q *= a[i].q;
| ^
shymbulak.cpp:166:17: error: '__gnu_cxx::__alloc_traits<std::allocator<el>, el>::value_type' {aka 'struct el'} has no member named 'q'
166 | cur.q *= a[i].q;
| ^
shymbulak.cpp:169:8: error: 'struct el' has no member named 'q'
169 | ans.q += cur.q;
| ^
shymbulak.cpp:169:17: error: 'struct el' has no member named 'q'
169 | ans.q += cur.q;
| ^
shymbulak.cpp:172:14: error: 'struct el' has no member named 'q'
172 | cout << ans.q << '\n';
| ^
