#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
const ll INF = 1e17 + 10ll;
const ll N = 2*1e5 + 10;
ll n;
vector<ll> adj[N];
ll maxoutdist[N];
ll out[N];
ll maxi = 0;
ll nummaxi = 0;
ll h[N];
void update(ll ans, ll numways) {
if (ans > maxi) {
maxi = ans;
nummaxi = numways;
} else if (ans == maxi) nummaxi += numways;
}
map<ll, vector<int>> cntheights[N];
void dfs4(ll cur, ll p) {
for (auto val: adj[cur]) {
if (val != p) {
dfs4(val, cur);
int sum = 0;
for (auto e: cntheights[val][h[val]]) sum+=e;
cntheights[cur][h[val] + 1].pb(sum);
}
}
if (adj[cur].size() == 1) cntheights[cur][0].pb(1);
}
int numout[N];
void dfs1(ll cur, ll p) {
vector<ll > heights;
// map<ll, ll> cntheights;
for (auto val: adj[cur]) {
if (val != p) {
heights.pb(h[val] + 1);
}
}
if (out[cur] != 0) {
heights.pb(out[cur]);
cntheights[cur][out[cur]].pb(numout[cur]);
}
sort(heights.rbegin(), heights.rend());
if (heights.size() >= 3) {
cout << cur << heights[0] << heights[1] << heights[2] << endl;
ll numways = 0;
// cntheights[heights[0]]--;
int sum = 0;
if (heights[1]==heights[2]) {
for (auto val: cntheights[cur][heights[1]]) sum += val;
for (auto val: cntheights[cur][heights[1]]) numways += val * (sum - val);
numways/=2;
// numways = (cntheights[heights[1]] * (cntheights[heights[1]] - 1ll)/2ll);
}
else {
int s1 = 0;
for (auto val: cntheights[cur][heights[1]]) s1 += val;
int s2 = 0;
for (auto val: cntheights[cur][heights[2]]) s2 += val;
for (auto val: cntheights[cur][heights[1]]) numways = s1*s2;
}
update(heights[0] * (heights[1] + heights[2]), numways);
// cout << numways << endl;
}
for (auto val: adj[cur]) {
if (val != p) dfs1(val, cur);
}
}
void dfs0(ll cur, ll p) {
// cout << cur << endl;
vector<ll> heights ={0, 0, 0};
for (auto val: adj[cur]) if (val != p) heights.pb(h[val] + 2);
sort(heights.rbegin(), heights.rend());
for (auto val: adj[cur]) {
if (val != p) {
ll curopt = heights[0];
if (h[val] + 2 == curopt) curopt = heights[1];
if (curopt < out[cur] + 1) {
curopt = out[cur]+1;
numout[val] = numout[cur];
} else if (curopt == out[cur] + 1) numout[val] += numout[cur];
out[val] = max(out[val], curopt);
dfs0(val, cur);
}
}
}
void dfs(ll cur, ll p) { // get all heights
vector<ll> heights;
map<ll, ll> cntheights;
for (auto val: adj[cur]) {
if (val != p) {
dfs(val, cur);
h[cur] = max(h[val] + 1, h[cur]);
}
}
}
int main() {
cin >> n;
for (ll i = 0; i < n -1; i++ ) {
ll a, b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
numout[1] = 1;
dfs(1, -1);
dfs0(1, -1);
dfs4(1, -1);
dfs1(1, -1);
if (maxi == 0) nummaxi = 1;
cout << maxi << ' ' << nummaxi << endl;
}
Compilation message
crocodile.cpp: In function 'void dfs1(ll, ll)':
crocodile.cpp:79:14: warning: unused variable 'val' [-Wunused-variable]
79 | for (auto val: cntheights[cur][heights[1]]) numways = s1*s2;
| ^~~
/usr/bin/ld: /tmp/ccN0Ql3k.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccWYQhhj.o:crocodile.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccN0Ql3k.o: in function `main':
grader.cpp:(.text.startup+0x36): undefined reference to `travel_plan(int, int, int (*) [2], int*, int, int*)'
collect2: error: ld returned 1 exit status
