#include<bits/stdc++.h>
using namespace std;
const long long maxn=500000+10;
long long n;
vector<long long>adj[maxn];
vector<pair<long long,long long>>alldp[maxn],ps[maxn],suf[maxn];
long long c2(long long a){
long long ret=a;
ret=ret*(ret-1)/2;
return ret;
}
pair<long long,long long>comp(pair<long long,long long>a,pair<long long,long long>b){
pair<long long,long long>ret=a;
if(a.first==b.first){
a.second+=b.first;
}else if(b.first>a.first){
ret=b;
}
if(ret.first==0){
ret.second=max(1ll,ret.second);
}
return ret;
}
void vorod(){
cin>>n;
for(long long i=0;i<n-1;i++){
long long u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
pair<long long,long long> dfsdown(long long u=1,long long par=-1){
if(par!=-1){
sort(adj[u].begin(),adj[u].end());
adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par));
}
pair<long long,long long>ret=make_pair(0,1);
for(auto x:adj[u]){
if(x==par){
continue;
}
pair<long long,long long>hey=dfsdown(x,u);
hey.first++;
alldp[u].push_back(hey);
if(hey.first==ret.first){
ret.second+=hey.second;
}else{
ret=max(ret,hey);
}
}
return ret;
}
void preall(long long ind){
long long sz=alldp[ind].size();
ps[ind].resize(sz+1);
suf[ind].resize(sz+1);
for(long long i=1;i<=sz;i++){
if(ps[ind][i-1].first==alldp[ind][i].first){
ps[ind][i].first=alldp[ind][i].first;
ps[ind][i].second=alldp[ind][i].second+ps[ind][i-1].second;
}else{
ps[ind][i]=max(ps[ind][i-1],alldp[ind][i-1]);
}
}
for(long long i=sz-1;i>=0;i--){
if(suf[ind][i+1].first==alldp[ind][i].first){
suf[ind][i].first=alldp[ind][i].first;
suf[ind][i].second=alldp[ind][i].second+suf[ind][i+1].second;
}else{
suf[ind][i]=max(suf[ind][i+1],alldp[ind][i]);
}
}
}
pair<long long,long long>ft[maxn];
void dfsup(long long u=1,long long par=-1){
for(long long i=0;i<(long long)adj[u].size();i++){
long long x=adj[u][i];
// cout<<"pas: "<<u<<" "<<i<<" "<<x<<" "<<ps[u][i].first<<" "<<suf[u][i].first<<endl;
ft[x]=comp(ft[u],comp(ps[u][i],suf[u][i+1]));
ft[x].first++;
dfsup(x,u);
}
if(par!=-1){
alldp[u].push_back(ft[u]);
}
}
void pre(){
dfsdown();
for(long long i=1;i<=n;i++){
preall(i);
}
dfsup();
}
long long cal(long long u){
if((long long)alldp[u].size()<3){
return 0;
}
sort(alldp[u].rbegin(),alldp[u].rend());
long long ret=alldp[u][0].first*(alldp[u][1].first+alldp[u][2].first);
return ret;
}
long long calted(long long u){
sort(alldp[u].rbegin(),alldp[u].rend());
// cout<<"hey: "<<u<<endl;
// for(auto x:alldp[u]){
// cout<<x.first<<" "<<x.second<<"\n";
// }
long long suma=0,ret=0;
for(auto x:alldp[u]){
if(x.first==alldp[u][2].first){
suma+=x.second;
}
}
if(alldp[u][2].first==alldp[u][1].first){
// cout<<"wtf: "<<suma<<" "<<c2(suma)<<endl;
ret+=c2(suma);
for(auto x:alldp[u]){
if(x.first==alldp[u][2].first)
ret-=c2(x.second);
}
return ret;
}
ret=suma*alldp[u][1].second;
return ret;
}
void solve(){
long long mainres=0;
for(long long i=1;i<=n;i++){
mainres=max(mainres,cal(i));
}
cout<<mainres<<" ";
long long ted=0;
for(long long i=1;i<=n;i++){
if(cal(i)==mainres&&mainres!=0){
ted+=calted(i);
}
}
if(mainres==0){
ted=1;
}
cout<<ted<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("inp.txt","r",stdin);
vorod();
pre();
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
48732 KB |
Output is correct |
2 |
Correct |
11 ms |
48732 KB |
Output is correct |
3 |
Correct |
11 ms |
48732 KB |
Output is correct |
4 |
Correct |
12 ms |
48732 KB |
Output is correct |
5 |
Correct |
11 ms |
48852 KB |
Output is correct |
6 |
Correct |
11 ms |
48732 KB |
Output is correct |
7 |
Correct |
11 ms |
48732 KB |
Output is correct |
8 |
Correct |
11 ms |
48732 KB |
Output is correct |
9 |
Correct |
11 ms |
48732 KB |
Output is correct |
10 |
Correct |
11 ms |
48732 KB |
Output is correct |
11 |
Correct |
11 ms |
48732 KB |
Output is correct |
12 |
Correct |
13 ms |
48732 KB |
Output is correct |
13 |
Correct |
11 ms |
48732 KB |
Output is correct |
14 |
Correct |
12 ms |
48732 KB |
Output is correct |
15 |
Correct |
11 ms |
48732 KB |
Output is correct |
16 |
Correct |
11 ms |
48732 KB |
Output is correct |
17 |
Correct |
11 ms |
48728 KB |
Output is correct |
18 |
Correct |
11 ms |
48732 KB |
Output is correct |
19 |
Correct |
11 ms |
48836 KB |
Output is correct |
20 |
Correct |
11 ms |
48732 KB |
Output is correct |
21 |
Correct |
11 ms |
48832 KB |
Output is correct |
22 |
Correct |
11 ms |
48732 KB |
Output is correct |
23 |
Correct |
11 ms |
48732 KB |
Output is correct |
24 |
Correct |
11 ms |
48728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
48732 KB |
Output is correct |
2 |
Correct |
11 ms |
48732 KB |
Output is correct |
3 |
Correct |
11 ms |
48732 KB |
Output is correct |
4 |
Correct |
12 ms |
48732 KB |
Output is correct |
5 |
Correct |
11 ms |
48852 KB |
Output is correct |
6 |
Correct |
11 ms |
48732 KB |
Output is correct |
7 |
Correct |
11 ms |
48732 KB |
Output is correct |
8 |
Correct |
11 ms |
48732 KB |
Output is correct |
9 |
Correct |
11 ms |
48732 KB |
Output is correct |
10 |
Correct |
11 ms |
48732 KB |
Output is correct |
11 |
Correct |
11 ms |
48732 KB |
Output is correct |
12 |
Correct |
13 ms |
48732 KB |
Output is correct |
13 |
Correct |
11 ms |
48732 KB |
Output is correct |
14 |
Correct |
12 ms |
48732 KB |
Output is correct |
15 |
Correct |
11 ms |
48732 KB |
Output is correct |
16 |
Correct |
11 ms |
48732 KB |
Output is correct |
17 |
Correct |
11 ms |
48728 KB |
Output is correct |
18 |
Correct |
11 ms |
48732 KB |
Output is correct |
19 |
Correct |
11 ms |
48836 KB |
Output is correct |
20 |
Correct |
11 ms |
48732 KB |
Output is correct |
21 |
Correct |
11 ms |
48832 KB |
Output is correct |
22 |
Correct |
11 ms |
48732 KB |
Output is correct |
23 |
Correct |
11 ms |
48732 KB |
Output is correct |
24 |
Correct |
11 ms |
48728 KB |
Output is correct |
25 |
Correct |
14 ms |
49840 KB |
Output is correct |
26 |
Correct |
14 ms |
50012 KB |
Output is correct |
27 |
Correct |
14 ms |
50008 KB |
Output is correct |
28 |
Correct |
14 ms |
50012 KB |
Output is correct |
29 |
Correct |
14 ms |
50008 KB |
Output is correct |
30 |
Correct |
14 ms |
50012 KB |
Output is correct |
31 |
Correct |
14 ms |
50012 KB |
Output is correct |
32 |
Correct |
15 ms |
50016 KB |
Output is correct |
33 |
Correct |
14 ms |
50012 KB |
Output is correct |
34 |
Correct |
14 ms |
50012 KB |
Output is correct |
35 |
Correct |
14 ms |
50008 KB |
Output is correct |
36 |
Correct |
15 ms |
50268 KB |
Output is correct |
37 |
Correct |
14 ms |
50264 KB |
Output is correct |
38 |
Correct |
16 ms |
50268 KB |
Output is correct |
39 |
Correct |
14 ms |
49928 KB |
Output is correct |
40 |
Correct |
14 ms |
49888 KB |
Output is correct |
41 |
Correct |
13 ms |
49900 KB |
Output is correct |
42 |
Correct |
14 ms |
49756 KB |
Output is correct |
43 |
Correct |
14 ms |
49752 KB |
Output is correct |
44 |
Correct |
15 ms |
49752 KB |
Output is correct |
45 |
Correct |
13 ms |
49756 KB |
Output is correct |
46 |
Correct |
13 ms |
49500 KB |
Output is correct |
47 |
Correct |
15 ms |
49756 KB |
Output is correct |
48 |
Correct |
13 ms |
49756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
48732 KB |
Output is correct |
2 |
Correct |
11 ms |
48732 KB |
Output is correct |
3 |
Correct |
11 ms |
48732 KB |
Output is correct |
4 |
Correct |
12 ms |
48732 KB |
Output is correct |
5 |
Correct |
11 ms |
48852 KB |
Output is correct |
6 |
Correct |
11 ms |
48732 KB |
Output is correct |
7 |
Correct |
11 ms |
48732 KB |
Output is correct |
8 |
Correct |
11 ms |
48732 KB |
Output is correct |
9 |
Correct |
11 ms |
48732 KB |
Output is correct |
10 |
Correct |
11 ms |
48732 KB |
Output is correct |
11 |
Correct |
11 ms |
48732 KB |
Output is correct |
12 |
Correct |
13 ms |
48732 KB |
Output is correct |
13 |
Correct |
11 ms |
48732 KB |
Output is correct |
14 |
Correct |
12 ms |
48732 KB |
Output is correct |
15 |
Correct |
11 ms |
48732 KB |
Output is correct |
16 |
Correct |
11 ms |
48732 KB |
Output is correct |
17 |
Correct |
11 ms |
48728 KB |
Output is correct |
18 |
Correct |
11 ms |
48732 KB |
Output is correct |
19 |
Correct |
11 ms |
48836 KB |
Output is correct |
20 |
Correct |
11 ms |
48732 KB |
Output is correct |
21 |
Correct |
11 ms |
48832 KB |
Output is correct |
22 |
Correct |
11 ms |
48732 KB |
Output is correct |
23 |
Correct |
11 ms |
48732 KB |
Output is correct |
24 |
Correct |
11 ms |
48728 KB |
Output is correct |
25 |
Correct |
14 ms |
49840 KB |
Output is correct |
26 |
Correct |
14 ms |
50012 KB |
Output is correct |
27 |
Correct |
14 ms |
50008 KB |
Output is correct |
28 |
Correct |
14 ms |
50012 KB |
Output is correct |
29 |
Correct |
14 ms |
50008 KB |
Output is correct |
30 |
Correct |
14 ms |
50012 KB |
Output is correct |
31 |
Correct |
14 ms |
50012 KB |
Output is correct |
32 |
Correct |
15 ms |
50016 KB |
Output is correct |
33 |
Correct |
14 ms |
50012 KB |
Output is correct |
34 |
Correct |
14 ms |
50012 KB |
Output is correct |
35 |
Correct |
14 ms |
50008 KB |
Output is correct |
36 |
Correct |
15 ms |
50268 KB |
Output is correct |
37 |
Correct |
14 ms |
50264 KB |
Output is correct |
38 |
Correct |
16 ms |
50268 KB |
Output is correct |
39 |
Correct |
14 ms |
49928 KB |
Output is correct |
40 |
Correct |
14 ms |
49888 KB |
Output is correct |
41 |
Correct |
13 ms |
49900 KB |
Output is correct |
42 |
Correct |
14 ms |
49756 KB |
Output is correct |
43 |
Correct |
14 ms |
49752 KB |
Output is correct |
44 |
Correct |
15 ms |
49752 KB |
Output is correct |
45 |
Correct |
13 ms |
49756 KB |
Output is correct |
46 |
Correct |
13 ms |
49500 KB |
Output is correct |
47 |
Correct |
15 ms |
49756 KB |
Output is correct |
48 |
Correct |
13 ms |
49756 KB |
Output is correct |
49 |
Correct |
618 ms |
167012 KB |
Output is correct |
50 |
Correct |
596 ms |
171604 KB |
Output is correct |
51 |
Correct |
610 ms |
175228 KB |
Output is correct |
52 |
Correct |
630 ms |
161984 KB |
Output is correct |
53 |
Correct |
631 ms |
174656 KB |
Output is correct |
54 |
Correct |
626 ms |
185632 KB |
Output is correct |
55 |
Correct |
600 ms |
175744 KB |
Output is correct |
56 |
Correct |
656 ms |
180152 KB |
Output is correct |
57 |
Correct |
569 ms |
182696 KB |
Output is correct |
58 |
Correct |
585 ms |
177776 KB |
Output is correct |
59 |
Correct |
590 ms |
177748 KB |
Output is correct |
60 |
Correct |
553 ms |
175184 KB |
Output is correct |
61 |
Correct |
759 ms |
210768 KB |
Output is correct |
62 |
Correct |
812 ms |
199504 KB |
Output is correct |
63 |
Correct |
816 ms |
166300 KB |
Output is correct |
64 |
Correct |
797 ms |
158596 KB |
Output is correct |
65 |
Correct |
750 ms |
153548 KB |
Output is correct |
66 |
Correct |
788 ms |
150812 KB |
Output is correct |
67 |
Correct |
760 ms |
149332 KB |
Output is correct |
68 |
Correct |
784 ms |
148868 KB |
Output is correct |
69 |
Correct |
789 ms |
148512 KB |
Output is correct |
70 |
Correct |
725 ms |
148952 KB |
Output is correct |
71 |
Correct |
718 ms |
147984 KB |
Output is correct |
72 |
Correct |
773 ms |
148396 KB |
Output is correct |
73 |
Correct |
759 ms |
148428 KB |
Output is correct |
74 |
Correct |
758 ms |
148936 KB |
Output is correct |
75 |
Correct |
747 ms |
149696 KB |
Output is correct |
76 |
Correct |
657 ms |
149192 KB |
Output is correct |
77 |
Correct |
488 ms |
150204 KB |
Output is correct |
78 |
Correct |
332 ms |
152344 KB |
Output is correct |