#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], H[N], M[N];
int mxd[N], cnt[N];
int counter[N * 2];
int diam; /* Answer */
ll cnt_diam; /* Answer */
vector < int > Adj[N], cyc;
int DFS_cyc(int v, int p)
{
M[v] = 1;
for (int &u : Adj[v])
if (u != p && M[u] <= 1)
{
if (M[u])
{
cyc.pb(v);
rev[v] = (int)cyc.size();
return (u);
}
int w = DFS_cyc(u, v);
if (w == -1)
continue;
if (w == -2)
return (-2);
cyc.pb(v);
rev[v] = (int)cyc.size();
if (w == v)
return -2;
return (w);
}
return (-1);
}
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]];
SS.erase(SS.lower_bound(mxd[cyc[i]] - i));
}
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 ... */
DFS_cyc(1, 0);
/* 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 main()':
shymbulak.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
shymbulak.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &v, &u);
~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
5992 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
57 ms |
10972 KB |
Output is correct |
| 2 |
Correct |
62 ms |
11512 KB |
Output is correct |
| 3 |
Correct |
57 ms |
15956 KB |
Output is correct |
| 4 |
Correct |
42 ms |
11768 KB |
Output is correct |
| 5 |
Correct |
46 ms |
11768 KB |
Output is correct |
| 6 |
Correct |
162 ms |
15864 KB |
Output is correct |
| 7 |
Correct |
111 ms |
13940 KB |
Output is correct |
| 8 |
Correct |
85 ms |
17656 KB |
Output is correct |
| 9 |
Correct |
85 ms |
17256 KB |
Output is correct |
| 10 |
Correct |
91 ms |
18632 KB |
Output is correct |
| 11 |
Incorrect |
99 ms |
17100 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
