#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;
typedef pair < int , int > ii;
typedef pair < int , ii > iii;
int n, m, cvp, kac = 1, u[N];
vector < int > g[N], b;
ii c[N];
ii uz(int i, int j){
int uz1 = j - i;
int uz2 = m - uz1;
if(uz1 != uz2)
return mp( min(uz1, uz2) , 1);
return mp(uz1, 2);
}
void yap(int sonmx, int xx){
if(sonmx == cvp)
kac += xx;
if(sonmx > cvp){
cvp = sonmx;
kac = xx;
}
}
int dfs(int node, int par){
u[node] = 1;
for(int i = 0; i < g[node].size(); i++)
if(g[node][i] != par) {
if(u[ g[node][i] ]){
b.pb(node);
return g[node][i];
}
int amk;
amk = dfs(g[node][i], node);
if(amk){
b.pb(node);
if(amk == node)
return 0;
else
return amk;
}
}
return 0;
}
ii bul(int node, int par){
int mx = 0, say = 1, son = -1, top = 0, mx2 = 0;
vector < ii > c;
vector < int > pre;
for(int i = 0; i < g[node].size(); i++)
if(g[node][i] != par and !u[g[node][i]]){
ii don = bul(g[node][i], node);
c.pb(mp(don.st + 1, don.nd));
pre.pb(0);
}
sort(c.begin(), c.end());
reverse(c.begin(), c.end());
for(int i = 0; i < c.size(); i++){
if(c[i].st == c[0].st){
pre[i] = ((i == 0)?0:pre[i-1]) + c[i].nd;
son = i;
}else if(c[i].st == c[son + 1].st){
top += c[i].nd;
mx2 = c[i].st;
}
}
if(son != -1){
mx = c[0].st, say = pre[son];
int sonmx = mx;
int xx = say;
yap(sonmx, xx);
}
if(son > 0){
int sonmx = c[0].st + c[0].st;
int xx = 0;
for(int i = 1; i <= son; i++)
xx += pre[i - 1]*c[i].nd;
yap(sonmx, xx);
}
if(son == 0){
int sonmx = c[0].st + mx2;
int xx = (c[0].nd)*top;
yap(sonmx, xx);
}
// cout << node << " -> " << mx << " , " << say << endl;
return mp(mx, say);
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d",&n);
for(int i = 1; i <= n; i++){
int u, v;
scanf("%d %d",&u ,&v);
g[u].pb(v);
g[v].pb(u);
}
b.pb(0);
dfs(1, 1);
memset(u, 0, sizeof u);
// for(int i = 1; i < b.size(); i++)cout << b[i] << " ";cout << endl;
for(int i = 1; i < b.size(); i++)u[b[i]] = 1;
for(int i = 1; i < b.size(); i++)
c[++m] = bul(b[i], -1);
for(int i = 1; i <= m; i++)
for(int j = i + 1; j <= m; j++){
int sonmx = uz(i, j).st + c[i].st + c[j].st;
int xx = uz(i, j).nd*c[i].nd*c[j].nd;
yap(sonmx, xx);
}
printf("%d\n", kac);
return 0;
}
Compilation message
shymbulak.cpp: In function 'int dfs(int, int)':
shymbulak.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'ii bul(int, int)':
shymbulak.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
shymbulak.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < c.size(); i++){
~~^~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < b.size(); i++)u[b[i]] = 1;
~~^~~~~~~~~~
shymbulak.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < b.size(); i++)
~~^~~~~~~~~~
shymbulak.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
shymbulak.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&u ,&v);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
27640 KB |
Output is correct |
| 2 |
Correct |
25 ms |
27748 KB |
Output is correct |
| 3 |
Correct |
24 ms |
27824 KB |
Output is correct |
| 4 |
Correct |
26 ms |
27824 KB |
Output is correct |
| 5 |
Correct |
25 ms |
27824 KB |
Output is correct |
| 6 |
Correct |
28 ms |
27876 KB |
Output is correct |
| 7 |
Correct |
29 ms |
28004 KB |
Output is correct |
| 8 |
Correct |
28 ms |
28004 KB |
Output is correct |
| 9 |
Correct |
26 ms |
28004 KB |
Output is correct |
| 10 |
Correct |
32 ms |
28012 KB |
Output is correct |
| 11 |
Correct |
29 ms |
28028 KB |
Output is correct |
| 12 |
Correct |
26 ms |
28028 KB |
Output is correct |
| 13 |
Correct |
33 ms |
28028 KB |
Output is correct |
| 14 |
Correct |
30 ms |
28028 KB |
Output is correct |
| 15 |
Correct |
26 ms |
28028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
28028 KB |
Output is correct |
| 2 |
Correct |
26 ms |
28156 KB |
Output is correct |
| 3 |
Correct |
31 ms |
28156 KB |
Output is correct |
| 4 |
Correct |
27 ms |
28156 KB |
Output is correct |
| 5 |
Correct |
31 ms |
28156 KB |
Output is correct |
| 6 |
Correct |
28 ms |
28224 KB |
Output is correct |
| 7 |
Correct |
30 ms |
28224 KB |
Output is correct |
| 8 |
Correct |
29 ms |
28224 KB |
Output is correct |
| 9 |
Correct |
28 ms |
28224 KB |
Output is correct |
| 10 |
Correct |
30 ms |
28224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
31084 KB |
Output is correct |
| 2 |
Correct |
155 ms |
31276 KB |
Output is correct |
| 3 |
Execution timed out |
1574 ms |
34172 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
