#include <bits/stdc++.h>
#define ld long double
#define ll long long
#define F first
#define S second
#define pb push_back
#define mp make_pair
using namespace std;
const ll inf = 1e18 + 18;
const int maxn = 200005;
int used[maxn];
bool cycle[maxn];
int depth[maxn];
pair <int, int> cc[maxn]; // {len, cnt}
vector <int> g[maxn];
int cyclesz = 0;
struct vert
{
int mx1;
int mx2;
int cnt1;
int cnt2;
vert(void)
{
mx1 = 0;
mx2 = 0;
cnt1 = 1;
cnt2 = 1;
}
};
vert sos(vert v1, vert v2)
{
vector <pair <int, int>> v;
v.pb({v1.mx1, v1.cnt1});
v.pb({v1.mx2, v1.cnt2});
v.pb({v2.mx1, v2.cnt1});
v.pb({v2.mx2, v2.cnt2});
sort(v.rbegin(), v.rend());
vert res;
res.mx1 = v[0].F;
res.cnt1 = v[0].S;
res.mx2 = v[1].F;
res.cnt2 = v[1].S;
return res;
}
vector <int> path;
bool f = false;
void findcycle(int v, int pr)
{
used[v] = 1;
path.pb(v);
for(int to:g[v])
{
if (used[to] == 0)
{
findcycle(to, v);
if (f) return; //
}
if (used[to] == 1 && pr != to)
{
f = true;
cycle[to] = true;
cyclesz = 1;
while(path.back() != to)
{
cycle[path.back()] = true;
path.pop_back();
cyclesz++;
}
return;
}
}
path.pop_back();
used[v] = 2;
return;
}
int maxdepth;
int maxdepth2;
int cnt;
int cnt2;
int len = 0;
int ans = 0; //ll
vert dfs(int v, int pr, int Depth)
{
vert vv;
vv.mx1 = 0;
vv.mx2 = 0;
vv.cnt1 = 0;
vv.cnt2 = 0;
if (int(g[v].size() == 1))
{
vv.mx1 = Depth;
vv.cnt1 = 1;
}
if (Depth > maxdepth2 && int(g[v].size() == 1))
{
maxdepth2 = Depth;
cnt2 = 1;
}
else
if (Depth == maxdepth2 && int(g[v].size() == 1))
{
cnt2++;
}
if (maxdepth2 > maxdepth && int(g[v].size() == 1))
{
swap(maxdepth, maxdepth2);
swap(cnt, cnt2);
}
else
if (maxdepth == Depth && int(g[v].size() == 1))
{
cnt++;
}
depth[v] = Depth;
for(int to:g[v])
{
if (to != pr && !cycle[to])
{
vv = sos(dfs(to, v, Depth + 1), vv);
}
}
if (vv.mx1 + vv.mx2 - Depth * 2 > len)
{
len = vv.mx1 + vv.mx2 - Depth * 2;
if (vv.cnt1 == 1)ans = vv.cnt1 * vv.cnt2 * 2;
else ans = vv.cnt1 * (vv.cnt1 - 1);
}
else
if (vv.mx1 + vv.mx2 - Depth * 2 == len)
{
if (vv.cnt1 == 1) ans += vv.cnt1 * vv.cnt2 * 2;
else ans += vv.cnt1 * (vv.cnt1 - 1);
}
if (vv.mx1 == vv.mx2)
{
vv.cnt1 += vv.cnt2;
vv.mx2 = 0;
}
return vv;
}
main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
x--;
y--;
g[x].pb(y);
g[y].pb(x);
}
findcycle(0, 0);
for(int i = 0; i < n; i++)
{
if (cycle[i])
{
maxdepth = 0;
maxdepth2 = 0;
cnt = 1;
cnt2 = 0;
vert vv = dfs(i, i, 0);
cc[i] = {maxdepth, cnt};
if (vv.mx1 + vv.mx2 > len)
{
len = vv.mx1 + vv.mx2;
if (vv.cnt1 == 1)ans = vv.cnt1 * vv.cnt2 * 2;
else ans = vv.cnt1 * (vv.cnt1 - 1);
}
else
if (vv.mx1 + vv.mx2 == len)
{
if (vv.cnt1 == 1) ans += vv.cnt1 * vv.cnt2 * 2;
else ans += vv.cnt1 * (vv.cnt1 - 1);
}
}
}
for(int i = 0; i < n; i++)
{
if (cycle[i])
{
for(int j:g[i])
{
if (cycle[j])
{
//obhod
int v = j;
int pr = i;
int LEN = cc[i].F;
int CNT = cc[i].S;
int t = (cyclesz >> 1);
for(t; t > 0; t--)
{
LEN++;
int to = -1;
for(auto ttt:g[v])
{
if (cycle[ttt] && ttt != pr)
{
to = ttt;
break;
}
}
if (LEN + cc[to].F > len)
{
len = LEN + cc[to].F;
ans = CNT * cc[to].S;
}
else
if (LEN + cc[to].F == len)
{
ans += CNT * cc[to].S;
}
}
}
}
}
}
// cerr << len << endl;
cout << (ans >> 1);
return 0;
}
Compilation message
shymbulak.cpp:159:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:221:26: warning: statement has no effect [-Wunused-value]
for(t; t > 0; t--)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
4992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
8760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
