#include <cstdio>
#include <vector>
const int N = 200000;
std::vector<int> g[N], c;
int n;
bool u[N], cyc[N];
int go(int v, int pr = -1)
{
u[v] = 1;
for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != pr) {
if (u[g[v][i]]) {
cyc[v] = 1;
cyc[g[v][i]] = 1;
c.push_back(g[v][i]);
c.push_back(v);
return 1;
}
int k;
if (k = go(g[v][i], v)) {
if (k == -1 || c.front() == v) return -1;
cyc[v] = 1;
c.push_back(v);
return 1;
}
}
return 0;
}
struct item {
int max;
long long amt;
item(int max_ = (1 << 31) >> 2, long long amt_ = 0) {
max = max_;
amt = amt_;
}
item operator+(item arg) {
item res;
res.max = std::max(max, arg.max);
if (res.max == max) res.amt += amt;
if (res.max == arg.max) res.amt += arg.amt;
return res;
}
} t[N << 2];
item fres;
int last;
void far(int v, int cur = 0, int pr = -1)
{
fres = fres + item(cur, 1);
if (fres.max == cur) last = v;
for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != pr && !cyc[g[v][i]]) far(g[v][i], cur + 1, v);
}
std::vector<int> path;
bool find(int v, int d, int pr = -1)
{
if (!d) {
path.push_back(v);
return 1;
}
for (int i = 0; i < (int)g[v].size(); ++i) if (!cyc[g[v][i]] && g[v][i] != pr && find(g[v][i], d - 1, v)) {
path.push_back(v);
return 1;
}
return 0;
}
item get(int l, int r)
{
item res;
for (l += c.size() << 1, r += c.size() << 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = res + t[l++];
if (r & 1) res = res + t[--r];
}
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int a, b;
scanf("%d%d", &a, &b);
g[a - 1].push_back(b - 1);
g[b - 1].push_back(a - 1);
}
go(0);
item ans;
for (int i = 0; i < (int)c.size(); ++i) {
cyc[c[i]] = 0;
fres = item();
far(c[i]);
fres.max -= i;
t[c.size() * 2 + i] = fres;
fres.max -= c.size();
t[c.size() * 3 + i] = fres;
int from = last;
fres = item();
far(last);
path.clear();
find(from, fres.max);
item cur;
cur.max = path.size() - 1;
if (path.size() & 1) {
int c = path[(int)path.size() >> 1];
cyc[c] = 1;
int amt = 0;
for (int i = 0; i < (int)g[c].size(); ++i) if (!cyc[g[c][i]]) {
fres = item();
far(g[c][i]);
if (fres.max + 1 == path.size() / 2) {
cur.amt += fres.amt * amt;
amt += fres.amt;
}
}
cyc[c] = 0;
} else {
int u = path[path.size() >> 1], v = path[path.size() - 1 >> 1];
fres = item();
far(u, 0, v);
int amt = fres.amt;
fres = item();
far(v, 0, u);
cur.amt = fres.amt * amt;
}
ans = ans + cur;
cyc[c[i]] = 1;
}
for (int i = (int)c.size() * 2 - 1; i; --i) t[i] = t[i << 1 | 1] + t[i << 1];
for (int i = 0; i < (int)c.size(); ++i) {
item cur = get((c.size() + 1 >> 1) + i, c.size() + i);
cur.max += c.size() + i + t[c.size() * 2 + i].max + i;
cur.amt *= t[2 * c.size() + i].amt;
ans = ans + cur;
}
printf("%lld\n", ans.amt);
return 0;
}
Compilation message
shymbulak.cpp: In function 'int go(int, int)':
shymbulak.cpp:21:9: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
21 | if (k = go(g[v][i], v)) {
| ~~^~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if (fres.max + 1 == path.size() / 2) {
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
shymbulak.cpp:120:57: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
120 | int u = path[path.size() >> 1], v = path[path.size() - 1 >> 1];
| ~~~~~~~~~~~~^~~
shymbulak.cpp:133:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
133 | item cur = get((c.size() + 1 >> 1) + i, c.size() + i);
| ~~~~~~~~~^~~
shymbulak.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
shymbulak.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
17484 KB |
Output is correct |
| 2 |
Correct |
8 ms |
17484 KB |
Output is correct |
| 3 |
Correct |
8 ms |
17612 KB |
Output is correct |
| 4 |
Correct |
9 ms |
17492 KB |
Output is correct |
| 5 |
Correct |
9 ms |
17400 KB |
Output is correct |
| 6 |
Correct |
8 ms |
17464 KB |
Output is correct |
| 7 |
Correct |
10 ms |
17404 KB |
Output is correct |
| 8 |
Correct |
10 ms |
17516 KB |
Output is correct |
| 9 |
Correct |
8 ms |
17448 KB |
Output is correct |
| 10 |
Correct |
9 ms |
17508 KB |
Output is correct |
| 11 |
Correct |
8 ms |
17484 KB |
Output is correct |
| 12 |
Correct |
9 ms |
17484 KB |
Output is correct |
| 13 |
Correct |
8 ms |
17444 KB |
Output is correct |
| 14 |
Correct |
8 ms |
17464 KB |
Output is correct |
| 15 |
Correct |
8 ms |
17484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
17484 KB |
Output is correct |
| 2 |
Correct |
9 ms |
17500 KB |
Output is correct |
| 3 |
Correct |
9 ms |
17516 KB |
Output is correct |
| 4 |
Correct |
10 ms |
17484 KB |
Output is correct |
| 5 |
Correct |
14 ms |
17728 KB |
Output is correct |
| 6 |
Correct |
11 ms |
17652 KB |
Output is correct |
| 7 |
Correct |
11 ms |
17624 KB |
Output is correct |
| 8 |
Correct |
11 ms |
17648 KB |
Output is correct |
| 9 |
Correct |
10 ms |
17612 KB |
Output is correct |
| 10 |
Correct |
10 ms |
17732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
20636 KB |
Output is correct |
| 2 |
Correct |
56 ms |
22040 KB |
Output is correct |
| 3 |
Correct |
48 ms |
25424 KB |
Output is correct |
| 4 |
Correct |
49 ms |
21980 KB |
Output is correct |
| 5 |
Correct |
45 ms |
21996 KB |
Output is correct |
| 6 |
Correct |
148 ms |
25552 KB |
Output is correct |
| 7 |
Correct |
89 ms |
24004 KB |
Output is correct |
| 8 |
Correct |
83 ms |
26864 KB |
Output is correct |
| 9 |
Correct |
87 ms |
26816 KB |
Output is correct |
| 10 |
Correct |
80 ms |
27324 KB |
Output is correct |
| 11 |
Correct |
93 ms |
26616 KB |
Output is correct |
| 12 |
Correct |
97 ms |
27192 KB |
Output is correct |
