#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first
#define vs second
const int mod = 1000000007;
const int N = 500004;
vector<int> adj[N];
vector<int> dis[N];
pair<ll,ll> ans;
void merge(ll x , ll y){
if(x > ans.vf){
ans = mp(x,y);
}
else if(x == ans.vf){
ans.vs += y;
}
}
int dfs(int node, int par){
dis[node].pb(0);
for(int i : adj[node]){
if(i!=par){
dis[node].pb(dfs(i,node));
}
}
sort(all(dis[node]),greater<>());
return dis[node][0] + 1;
}
void cal(int node , int par , int val , int fre){
ll mx = dis[node][0];
ll cnt = 1;
for(int i = 1; i < dis[node].size(); i++){
if(dis[node][i] == mx)cnt++;
else break;
}
ll mx1 = -1 , cnt1 = 0;
if(cnt == 1){
mx1 = 0;
if(dis[node].size() > 1){
mx1 = dis[node][1];
for(int i = 1; i < dis[node].size(); i++){
if(dis[node][i] == mx1)cnt1++;
else break;
}
}
}
if(val > mx){
swap(mx,mx1);
swap(cnt,cnt1);
mx = val;
cnt = fre;
}
else if(val == mx){
cnt += fre;
}
else if(val > mx1){
mx1 = val;
cnt1 = fre;
}
else if(val == mx1){
cnt1 += fre;
}
for(int i : adj[node]){
if(i!=par){
if(dis[i][0] + 1 == mx){
if(cnt==1){
cal(i,node,mx1+1,cnt1);
}
else {
cal(i,node,mx+1,cnt-1);
}
}
}
}
if(dis[node].size() <= 2)return;
ll x = dis[node][0];
ll y = dis[node][1];
ll yf = 1;
for(int i = 2; i < dis[node].size(); i++){
if(dis[node][i] != yf)break;
yf++;
}
if(x != y){
merge((x+y)*val,fre*yf);
merge((x+val)*y,fre*yf);
merge((y+val)*x,fre*yf);
}
else {
yf++;
merge((x+y)*val,fre*((yf*(yf-1LL))/2));
merge((x+val)*y,fre*((yf*(yf-1LL))/2));
merge((y+val)*x,fre*((yf*(yf-1LL))/2));
}
}
void solve(){
int n;
cin >> n;
for(int i = 0; i < n - 1; i++){
int a , b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1,1);
ans=mp(0,1);
cal(1,1,0,0);
cout << ans.vf << ' ' << ans.vs << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
Compilation message
road.cpp: In function 'void cal(int, int, int, int)':
road.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i = 1; i < dis[node].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
road.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 1; i < dis[node].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
road.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i = 2; i < dis[node].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
5 ms |
23900 KB |
Output is correct |
| 3 |
Correct |
5 ms |
23944 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
23900 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
5 ms |
23900 KB |
Output is correct |
| 3 |
Correct |
5 ms |
23944 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
23900 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
5 ms |
23900 KB |
Output is correct |
| 3 |
Correct |
5 ms |
23944 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
23900 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
