#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);
}
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 1;
}
if(dfs(g[node][i], node)){
b.pb(node);
return 1;
}
}
return 0;
}
ii bul(int node, int par){
int mx = 0, say = 1, son = -1, son2 = -1;
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){
pre[i] = ((i == son + 1)?0:pre[i-1]) + c[i].nd;
son2 = i;
}
}
int sonmx = 0, xx = 1;
if(son != -1){
mx = c[0].st, say = pre[son];
sonmx = mx;
xx = say;
}
if(son > 0){
sonmx = c[0].st + c[0].st;
xx = 0;
for(int i = 1; i <= son; i++)
xx += pre[i - 1]*c[i].nd;
}
if(son == 0 and son2 > 0){
sonmx = c[0].st + c[son2].st;
xx = (c[0].nd)*pre[son2];
}
if(sonmx == cvp)
kac += xx;
if(sonmx > cvp){
cvp = sonmx;
kac = 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++)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, xx;
sonmx = uz(i, j).st + c[i].st + c[j].st;
xx = uz(i, j).nd*c[i].nd*c[j].nd;
if(sonmx == cvp)
kac += xx;
if(sonmx > cvp){
cvp = sonmx;
kac = xx;
}
}
printf("%d\n", kac);
return 0;
}
Compilation message
shymbulak.cpp: In function 'int dfs(int, int)':
shymbulak.cpp:26: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:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
shymbulak.cpp:52: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:102: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:103:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < b.size(); i++)
~~^~~~~~~~~~
shymbulak.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
shymbulak.cpp:95: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 |
24 ms |
27644 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
27748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
27784 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
27784 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
30804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
