#include<bits/stdc++.h>
using namespace std;
#define int long long
#define forn(i,j) for(int i = 0; i < j; i++)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define pb push_back
#define s second
#define all(x) x.begin(),x.end()
const int MOD = 1e9 + 7; const int INF = 1e17 + 1; const int maxN = 2e5 + 1;
void setIO(string name = ""){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(!name.empty()){
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
struct Node{
int d1 = 0, d2 = 0, d3 = 0;
void add(int a){
if(d1 < a){
int curr_d1 = d1; int curr_d2 = d2;
d1 = a; d2 = curr_d1; d3 = curr_d2;
return;
}
if(d2 < a){
int curr_d2 = d2;
d2 = a; d3 = curr_d2;
return;
}
d3 = max(d3,a);
}
};
vi graph[maxN]; Node vtx[maxN];
int subtree_dist[maxN];
void dfs(int src, int prev){
subtree_dist[src] = 0;
for(int ch : graph[src]){
if(ch == prev) continue;
dfs(ch,src);
subtree_dist[src] = max(subtree_dist[src],subtree_dist[ch]+1);
vtx[src].add(subtree_dist[ch]+1);
}
}
void dfs2(int src, int prev){
for(int ch : graph[src]){
if(ch == prev) continue;
if(subtree_dist[ch]+1 == vtx[src].d1){
vtx[ch].add(vtx[src].d2+1);
}
else{
vtx[ch].add(vtx[src].d1+1);
}
dfs2(ch,src);
}
}
signed main(){
setIO();
int n; cin >> n;
forn(i,n-1){
int a,b; cin >> a >> b;
graph[a].pb(b); graph[b].pb(a);
}
dfs(1,-1); dfs2(1,-1);
int ans = 0;
forrange(i,1,n+1){
if(vtx[i].d3 == 0) continue;
ans = max(ans,vtx[i].d1*(vtx[i].d2+vtx[i].d3));
}
int freq = 0;
if(ans == 0){
cout << ans << " " << 1 << endl;
return 0;
}
forrange(i,1,n+1){
if(vtx[i].d1*(vtx[i].d2+vtx[i].d3) == ans){
if(vtx[i].d1 == vtx[i].d2 && vtx[i].d3 != vtx[i].d1){
freq += 2; continue;
}
else if(vtx[i].d1 == vtx[i].d2 == vtx[i].d3){
freq += 3; continue;
}
freq++;
}
}
cout << ans << " " << freq << endl;
}
Compilation message
road.cpp: In function 'int main()':
road.cpp:107:22: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
107 | else if(vtx[i].d1 == vtx[i].d2 == vtx[i].d3){
| ~~~~~~~~~~^~~~~~~~~~~~
road.cpp: In function 'void setIO(std::string)':
road.cpp:22:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road.cpp:23:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 4 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 5 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 6 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 4 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 5 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 6 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 4 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 5 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 6 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
