#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 200005;
int n, rev[N], P[N], M[N];
int mxd[N], cnt[N];
int counter[N * 2];
int diam; /* Answer */
ll cnt_diam; /* Answer */
pair < int , int > vcu;
vector < int > Adj[N], cyc;
int DFS_cyc(int v, int p)
{
M[v] = 1; P[v] = p;
for (int &u : Adj[v])
if (u != p)
{
if (M[u] == 0)
DFS_cyc(u, v);
else if (M[u] == 1)
vcu.first = v, vcu.second = u;
}
M[v] = 2;
}
void DFS(int v, int p)
{
int xd[2] = {0, -N};
int xc[2] = {0, 0};
for (int &u : Adj[v])
if (u != p && !rev[u])
{
DFS(u, v);
if (xd[1] < mxd[u] + 1)
xd[1] = mxd[u] + 1;
if (xd[0] < xd[1])
swap(xd[0], xd[1]);
}
ll tot = 0;
for (int &u : Adj[v])
if (u != p && !rev[u])
{
if (xd[1] == mxd[u] + 1)
xc[1] += cnt[u];
if (xd[0] == mxd[u] + 1)
{
xc[0] += cnt[u];
if (xd[0] == xd[1])
tot -= 1LL * cnt[u] * cnt[u];
}
}
if (xd[0] == 0) xc[0] ++;
if (xd[1] == 0) xc[1] ++;
tot += 1LL * xc[0] * xc[1];
mxd[v] = xd[0];
cnt[v] = xc[0];
if (diam < xd[0] + xd[1])
diam = xd[0] + xd[1], cnt_diam = 0;
if (diam == xd[0] + xd[1])
cnt_diam += tot;
}
multiset < int > SS;
inline void Add(int i)
{
SS.insert(mxd[cyc[i]] - i);
counter[mxd[cyc[i]] - i + N] += cnt[cyc[i]];
}
inline void Del(int i)
{
counter[mxd[cyc[i]] - i + N] -= cnt[cyc[i]];
auto it = SS.lower_bound(mxd[cyc[i]] - i);
assert(it != SS.end() && (*it) == (mxd[cyc[i]] - i));
SS.erase(it);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int v, u;
scanf("%d%d", &v, &u);
Adj[v].pb(u);
Adj[u].pb(v);
}
/* Building the main cycle ... */
vcu = {-1, -1};
DFS_cyc(1, 0);
assert(vcu.first != -1);
assert(vcu.second != -1);
while (vcu.first != P[vcu.second])
{
cyc.pb(vcu.first);
rev[vcu.first] = (int)cyc.size();
vcu.first = P[vcu.first];
}
/* End of :: Building the main cycle ... */
/* finding diameter of the trees ... */
for (int i = 0; i < (int)cyc.size(); i++)
DFS(cyc[i], 0);
/* End of :: finding diameter of the trees ... */
/* Everything else ... */
int m = (int)cyc.size();
for (int i = 0; i < m; i++)
cyc.pb(cyc[i]);
for (int i = 0; i < (m >> 1); i++)
Add(i);
vector < int > mark(N, 0);
for (int i = (m >> 1); i < (int)cyc.size(); i++)
{
if (mark[cyc[i]])
break;
mark[cyc[i]] = 1;
if (diam < mxd[cyc[i]] + i + (*SS.rbegin()))
diam = mxd[cyc[i]] + i + (*SS.rbegin()), cnt_diam = 0;
if (diam == mxd[cyc[i]] + i + (*SS.rbegin()))
cnt_diam += 1LL * cnt[cyc[i]] * counter[(*SS.rbegin()) + N];
Del(i - (m >> 1));
Add(i);
}
return !printf("%lld\n", cnt_diam);
}
Compilation message
shymbulak.cpp: In function 'int DFS_cyc(int, int)':
shymbulak.cpp:27:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
shymbulak.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &v, &u);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
10488 KB |
Output is correct |
| 2 |
Correct |
63 ms |
10872 KB |
Output is correct |
| 3 |
Correct |
59 ms |
15264 KB |
Output is correct |
| 4 |
Correct |
46 ms |
11128 KB |
Output is correct |
| 5 |
Correct |
51 ms |
11088 KB |
Output is correct |
| 6 |
Correct |
198 ms |
14508 KB |
Output is correct |
| 7 |
Correct |
120 ms |
12940 KB |
Output is correct |
| 8 |
Correct |
99 ms |
16120 KB |
Output is correct |
| 9 |
Correct |
144 ms |
16052 KB |
Output is correct |
| 10 |
Correct |
92 ms |
17036 KB |
Output is correct |
| 11 |
Incorrect |
98 ms |
15584 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
