#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define m_p make_pair
const int N = 200005;
int n;
vector<int> a[N];
pair<int, int> b[N];
int pp[N];
int ss, ff;
int c[N];
bool dfs(int x, int p)
{
c[x] = 1;
pp[x] = p;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p)
continue;
if (c[h] == 1)
{
ss = h;
ff = x;
return true;
}
if (c[h] == 0)
if (dfs(h, x))
return true;
}
c[x] = 2;
return false;
}
vector<int> v;
void pre()
{
dfs(1, 0);
for (int x = ff; x != ss; x = pp[x])
v.push_back(x);
v.push_back(ss);
for (int i = 1; i <= n; ++i)
c[i] = 0;
for (int i = 0; i < v.size(); ++i)
c[v[i]] = 1;
}
int d[N];
void dfs1(int x, int p)
{
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p || c[h] == 1)
continue;
d[h] = d[x] + 1;
dfs1(h, x);
}
}
int dans[N];
long long ans[N];
int maxu[N];
long long q[N];
void dfs2(int x, int p)
{
bool zz = false;
int maxu1 = d[x], maxu2 = 0;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p || c[h] == 1)
continue;
zz = true;
dfs2(h, x);
if (maxu[h] > maxu1)
{
maxu2 = maxu1;
maxu1 = maxu[h];
}
else if (maxu[h] > maxu2)
maxu2 = maxu[h];
}
if (!zz)
{
maxu[x] = d[x];
q[x] = 1;
dans[x] = 0;
ans[x] = 1;
return;
}
dans[x] = maxu1 + maxu2 - 2 * d[x];
if (maxu1 != maxu2)
{
long long q1 = 0, q2 = 0;
if (d[x] == maxu1)
++q1;
if (d[x] == maxu2)
++q2;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p || c[h] == 1)
continue;
if (maxu[h] == maxu1)
q1 += q[h];
if (maxu[h] == maxu2)
q2 += q[h];
}
ans[x] = q1 * q2;
maxu[x] = maxu1;
q[x] = q1;
}
else
{
long long qm = 0;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p || c[h] == 1)
continue;
if (maxu[h] == maxu1)
qm += q[h];
}
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p || c[h] == 1)
continue;
if (maxu[h] == maxu1)
ans[x] += ((qm - q[h]) * q[h]);
}
ans[x] /= 2;
maxu[x] = maxu1;
q[x] = qm;
}
int maxud = dans[x];
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p || c[h] == 1)
continue;
maxud = max(maxud, dans[h]);
}
if (dans[x] != maxud)
{
dans[x] = maxud;
ans[x] = 0;
}
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p || c[h] == 1)
continue;
if (dans[h] == dans[x])
ans[x] += ans[h];
}
}
struct ban
{
int maxu;
long long q;
int laz;
ban(){}
ban(int maxu, long long q)
{
this->maxu = maxu;
this->q = q;
laz = 0;
}
};
ban t[N * 4];
void shi(int pos)
{
if (t[pos].laz == 0)
return;
t[pos * 2].maxu += t[pos].laz;
t[pos * 2 + 1].maxu += t[pos].laz;
t[pos * 2].laz += t[pos].laz;
t[pos * 2 + 1].laz += t[pos].laz;
t[pos].laz = 0;
}
ban mer(const ban& l, const ban& r)
{
ban res;
if (l.maxu > r.maxu)
res = l;
else if (l.maxu < r.maxu)
res = r;
else
{
res.maxu = l.maxu;
res.q = l.q + r.q;
}
res.laz = 0;
return res;
}
void bil(int tl, int tr, int pos)
{
if (tl == tr)
{
t[pos].maxu = maxu[v[tl]] + min(tl, (int)v.size() - tl);
t[pos].q = q[v[tl]];
t[pos].laz = 0;
return;
}
int m = (tl + tr) / 2;
bil(tl, m, pos * 2);
bil(m + 1, tr, pos * 2 + 1);
t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
void ubd(int tl, int tr, int l, int r, int y, int pos)
{
if (l > r)
return;
if (tl == l && tr == r)
{
t[pos].maxu += y;
t[pos].laz += y;
return;
}
shi(pos);
int m = (tl + tr) / 2;
if (r <= m)
ubd(tl, m, l, r, y, pos * 2);
else if (l > m)
ubd(m + 1, tr, l, r, y, pos * 2 + 1);
else
{
ubd(tl, m, l, m, y, pos * 2);
ubd(m + 1, tr, m + 1, r, y, pos * 2 + 1);
}
t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
ban qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return(ban(0, 0));
if (tl == l && tr == r)
return t[pos];
shi(pos);
int m = (tl + tr) / 2;
if (r <= m)
return qry(tl, m, l, r, pos * 2);
if (l > m)
return qry(m + 1, tr, l, r, pos * 2 + 1);
return mer(qry(tl, m, l, m, pos * 2), qry(m + 1, tr, m + 1, r, pos * 2 + 1));
}
int vdans[N];
long long vans[N];
void vqry(int i)
{
int u = (v.size() - 1) / 2;
if (v.size() % 2 == 1)
{
ban ll;
int l = i + 1, r = i + u;
if (l >= v.size() && r >= v.size())
{
l -= v.size();
r -= v.size();
}
if (r < v.size())
ll = qry(0, v.size() - 1, l, r, 1);
else
{
ll = mer(qry(0, v.size() - 1, l, v.size() - 1, 1), qry(0, v.size() - 1, 0, r - v.size(), 1));
}
ban rr;
l = i - u, r = i - 1;
if (l < 0 && r < 0)
{
l += v.size();
r += v.size();
}
if (l >= 0)
rr = qry(0, v.size() - 1, l, r, 1);
else
{
rr = mer(qry(0, v.size() - 1, 0, r, 1), qry(0, v.size() - 1, l + v.size(), v.size() - 1, 1));
}
ban res = mer(ll, rr);
vans[i] = res.q * q[v[i]];
vdans[i] = res.maxu + maxu[v[i]];
}
else
{
ban ll;
int l = i + 1, r = i + u;
if (l >= v.size() && r >= v.size())
{
l -= v.size();
r -= v.size();
}
if (r < v.size())
ll = qry(0, v.size() - 1, l, r, 1);
else
{
ll = mer(qry(0, v.size() - 1, l, v.size() - 1, 1), qry(0, v.size() - 1, 0, r - v.size(), 1));
}
ban rr;
l = i - u, r = i - 1;
if (l < 0 && r < 0)
{
l += v.size();
r += v.size();
}
if (l >= 0)
rr = qry(0, v.size() - 1, l, r, 1);
else
{
rr = mer(qry(0, v.size() - 1, 0, r, 1), qry(0, v.size() - 1, l + v.size(), v.size() - 1, 1));
}
ban res = mer(ll, rr);
res = mer(res, ban(maxu[v[(i + u + 1) % v.size()]] + u + 1, q[v[(i + u + 1) % v.size()]] * 2));
vans[i] = res.q * q[v[i]];
vdans[i] = res.maxu + maxu[v[i]];
}
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("shymbulak.in", "r", stdin);
//freopen("shymbulak.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
b[i] = m_p(x, y);
}
pre();
for (int i = 0; i < v.size(); ++i)
{
//cout << v[i] << ' ';
dfs1(v[i], 0);
dfs2(v[i], 0);
}
//cout << endl;
/*for (int i = 0; i < v.size(); ++i)
{
for (int j = 0; j < v.size(); ++j)
{
if (j == i)
continue;
if (maxu[v[j]] + min(abs(j - i), (int)v.size() - abs(j - i)) > vdans[i])
{
vdans[i] = maxu[v[j]] + min(abs(j - i), (int)v.size() - abs(j - i));
if (abs(j - i) == v.size() - abs(j - i))
vans[i] = q[v[j]] * 2;
else
vans[i] = q[v[j]];
}
else if (maxu[v[j]] + min(abs(j - i), (int)v.size() - abs(j - i)) == vdans[i])
{
if (abs(j - i) == v.size() - abs(j - i))
vans[i] += q[v[j]] * 2;
else
vans[i] += q[v[j]];
}
}
vdans[i] += maxu[v[i]];
vans[i] *= q[v[i]];
}*/
bil(0, v.size() - 1, 1);
vqry(0);
for (int i = 1; i < v.size(); ++i)
{
int u = v.size() / 2;
int l = i, r = i + u - 1;
if (l >= v.size() && r >= v.size())
{
l -= v.size();
r -= v.size();
}
if (r < v.size())
ubd(0, v.size() - 1, l, r, -1, 1);
else
{
ubd(0, v.size() - 1, l, v.size() - 1, -1, 1);
ubd(0, v.size() - 1, 0, r - v.size(), -1, 1);
}
l = i - u, r = i - 1;
if (l < 0 && r < 0)
{
l += v.size();
r += v.size();
}
if (l >= 0)
ubd(0, v.size() - 1, l, r, 1, 1);
else
{
ubd(0, v.size() - 1, 0, r, 1, 1);
ubd(0, v.size() - 1, l + v.size(), v.size() - 1, 1, 1);
}
vqry(i);
}
int maxuu = 0;
for (int i = 0; i < v.size(); ++i)
{
//cout << vdans[i] << ' ';
maxuu = max(maxuu, dans[v[i]]);
maxuu = max(maxuu, vdans[i]);
}
//cout << endl;
long long yans = 0, yyans = 0;
for (int i = 0; i < v.size(); ++i)
{
if (dans[v[i]] == maxuu)
yans += ans[v[i]];
if (vdans[i] == maxuu)
yyans += vans[i];
}
cout << yans + yyans / 2 << endl;
return 0;
}
Compilation message
shymbulak.cpp: In function 'bool dfs(int, int)':
shymbulak.cpp:21:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void pre()':
shymbulak.cpp:50:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); ++i)
~~^~~~~~~~~~
shymbulak.cpp: In function 'void dfs1(int, int)':
shymbulak.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(int, int)':
shymbulak.cpp:78:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
shymbulak.cpp:109:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
shymbulak.cpp:126:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
shymbulak.cpp:134:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
shymbulak.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
shymbulak.cpp:159:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void vqry(int)':
shymbulak.cpp:276:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l >= v.size() && r >= v.size())
~~^~~~~~~~~~~
shymbulak.cpp:276:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l >= v.size() && r >= v.size())
~~^~~~~~~~~~~
shymbulak.cpp:281:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (r < v.size())
~~^~~~~~~~~~
shymbulak.cpp:308:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l >= v.size() && r >= v.size())
~~^~~~~~~~~~~
shymbulak.cpp:308:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l >= v.size() && r >= v.size())
~~^~~~~~~~~~~
shymbulak.cpp:313:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (r < v.size())
~~^~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:354:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); ++i)
~~^~~~~~~~~~
shymbulak.cpp:390:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < v.size(); ++i)
~~^~~~~~~~~~
shymbulak.cpp:394:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l >= v.size() && r >= v.size())
~~^~~~~~~~~~~
shymbulak.cpp:394:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l >= v.size() && r >= v.size())
~~^~~~~~~~~~~
shymbulak.cpp:399:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (r < v.size())
~~^~~~~~~~~~
shymbulak.cpp:423:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); ++i)
~~^~~~~~~~~~
shymbulak.cpp:432:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); ++i)
~~^~~~~~~~~~
shymbulak.cpp:344:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
shymbulak.cpp:348:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5112 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5112 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5112 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5112 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5112 KB |
Output is correct |
| 11 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 12 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 13 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5116 KB |
Output is correct |
| 15 |
Correct |
6 ms |
5112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5624 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5496 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5496 KB |
Output is correct |
| 8 |
Correct |
8 ms |
5496 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5496 KB |
Output is correct |
| 10 |
Correct |
8 ms |
5496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
13148 KB |
Output is correct |
| 2 |
Correct |
58 ms |
13944 KB |
Output is correct |
| 3 |
Correct |
109 ms |
20004 KB |
Output is correct |
| 4 |
Correct |
48 ms |
13688 KB |
Output is correct |
| 5 |
Correct |
45 ms |
13688 KB |
Output is correct |
| 6 |
Correct |
173 ms |
20728 KB |
Output is correct |
| 7 |
Correct |
124 ms |
17524 KB |
Output is correct |
| 8 |
Correct |
90 ms |
22432 KB |
Output is correct |
| 9 |
Correct |
98 ms |
22292 KB |
Output is correct |
| 10 |
Correct |
94 ms |
23544 KB |
Output is correct |
| 11 |
Correct |
121 ms |
22248 KB |
Output is correct |
| 12 |
Correct |
149 ms |
23128 KB |
Output is correct |
