// #define DEBUG
// #define STRESS_TESTING
#define ALL__LL
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
typedef long long llong;
#ifdef ALL_LL
#define int long long
#endif
const int maxN = 500005;
vector<int> nei[maxN];
pair<int, int> ray[maxN][3];
map<llong, llong> ans;
vector<pair<int, int>> dists[maxN];
namespace AC
{
int n;
pair<int, int> maxdist[maxN];
bool used[maxN];
void MaxDist(int u);
pair<int, int> DFS(int u, int dep, int dist);
void Solve(int n_)
{
n = n_;
pair<int, int> ans(0, 0);
for (int u=1; u<=n; u++)
if (nei[u].size()==1)
{
memset(used+1, 0, n*sizeof(bool));
MaxDist(u);
memset(used+1, 0, n*sizeof(bool));
pair<int, int> curAns=DFS(u, 0, 0);
if (curAns.first>ans.first) ans=curAns;
else if (curAns.first==ans.first) ans.second+=curAns.second;
}
cout<<ans.first<<' '<<ans.second/2<<'\n';
}
pair<int, int> DFS(int u, int dep, int dist)
{
used[u]=true;
if (nei[u].size()==1 && used[nei[u][0]])
return make_pair(dep*dist, 1);
pair<int, int> ans(0, 0);
for (int i=0; i<nei[u].size(); i++)
{
int to=nei[u][i];
if (!used[to])
{
pair<int, int> curAns;
if (maxdist[u].first==maxdist[to].first+1)
curAns=DFS(to, dep+1, max(dist, maxdist[u].second));
else
curAns=DFS(to, dep+1, max(dist, maxdist[u].first));
if (curAns.first>ans.first) ans=curAns;
else if (curAns.first==ans.first) ans.second+=curAns.second;
}
}
return ans;
}
void MaxDist(int u)
{
used[u]=true;
maxdist[u]=make_pair(0, 0);
if (nei[u].size()==1 && used[nei[u][0]]) return;
for (int i=0; i<nei[u].size(); i++)
{
int to=nei[u][i];
if (!used[to])
{
MaxDist(to);
int temp=maxdist[to].first+1;
if (temp>maxdist[u].first)
{
swap(maxdist[u].first, maxdist[u].second);
maxdist[u].first=temp;
}
else if (temp>maxdist[u].second)
maxdist[u].second=temp;
}
}
}
};
inline ostream& operator<<(ostream& ostr, const pair<int, int>& a)
{
return ostr << "{" << a.first << ", " << a.second << "}";
}
void Maximize(pair<int, int>* a, pair<int, int> x)
{
if (a[0].first == x.first)
a[0].second += x.second;
else if (a[1].first == x.first)
a[1].second += x.second;
else if (a[2].first == x.first)
a[2].second += x.second;
else if (x.first > a[2].first)
{
a[2] = x;
sort(a, a + 3, greater<pair<int, int>>());
}
}
void SetDown(int v, int par)
{
fill(ray[v], ray[v] + 3, make_pair(0, 0));
ray[v][0] = {0, 1};
for (int to: nei[v])
if (to != par)
{
SetDown(to, v);
int val, cnt;
Maximize(ray[v], {(val = ray[to][0].first + 1), (cnt = ray[to][0].second/*1*/)});
if (val) dists[v].push_back({val, cnt});
}
}
void SetUp(int v, int par)
{
for (int to: nei[v])
if (to != par)
{
// Set up[to].
int val = 0, cnt = 0;
if (ray[v][0].first == ray[to][0].first + 1 && ray[v][0].second == ray[to][0].second)
Maximize(ray[to], {(val = ray[v][1].first + 1), (cnt = ray[v][1].second/*1*/)});
else if (ray[v][0].first == ray[to][0].first + 1)
Maximize(ray[to], {(val = ray[v][0].first + 1), (cnt = ray[v][0].second - ray[to][0].second/*1*/)});
else
Maximize(ray[to], {(val = ray[v][0].first + 1), (cnt = ray[v][0].second)});
if (val) dists[to].push_back({val, cnt});
SetUp(to, v);
}
sort(dists[v].begin(), dists[v].end(), greater<pair<int, int>>());
#ifdef DEBUG
cerr << "v: " << v << "\tdists: " << dists[v][0] << ' ';
if (dists[v].size() >= 2) cout << dists[v][1];
if (dists[v].size() >= 3) cout << ' ' << dists[v][2];
cout << endl;
#endif
if (dists[v].size() < 3) return;
bool eq = (dists[v][1].first == dists[v][2].first);
int cnt[2];
for (int i = 0; i < 3; ++i)
{
if (ray[v][i].first == dists[v][1].first)
cnt[0] = ray[v][i].second;
if (ray[v][i].first == dists[v][2].first)
cnt[1] = ray[v][i].second;
}
llong delta;
if (eq)
ans[dists[v][0].first * (dists[v][1].first + dists[v][2].first)] += (delta = (cnt[0] * (cnt[0] - 1LL)) / 2LL);
else
ans[dists[v][0].first * (dists[v][1].first + dists[v][2].first)] += (delta = (llong)cnt[0] * cnt[1]);
// Subtract x * (x - 1) / 2 for x = rays going to the same `to`
for (auto p: dists[v])
{
llong dlt;
if ((p.first == dists[v][1].first || p.first == dists[v][2].first) && dists[v][1].first == dists[v][2].first) // erkrord paymany petqa?
{
if (v == 3)
{
cerr << "Good.\tp = " << p << endl;
}
bool f = (p.first == dists[v][0].first);
// if (f) --p.second;
ans[dists[v][0].first * (dists[v][1].first + dists[v][2].first)] -=
(dlt = (p.second * (p.second - 1LL)) / 2LL);
// if (f) ++p.second;
#ifdef DEBUG
cerr << "v: " << v << "\tdelta = -" << dlt << endl;
#endif
}
}
#ifdef DEBUG
cerr << "v: " << v << "\tdelta = " << delta << endl;
#endif
}
#ifdef ALL_LL
#undef int
#endif
int main()
#ifdef ALL_LL
#define int long long
#endif
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
// cin >> n;
// n = rand() % 20 + 1;
#ifndef STRESS_TESTING
cin >> n;
#endif
#ifdef STRESS_TESTING
n = 9;
int seed;
cin >> seed;
srand(seed);
#endif
// cerr << n << endl;
for (int i = 1; i < n; ++i)
{
int u, v;
#ifndef STRESS_TESTING
cin >> u >> v;
#else
v = i + 1;
u = rand() % i + 1;
cerr << u << ' ' << v << endl;
#endif
nei[u].push_back(v);
nei[v].push_back(u);
}
SetDown(1, -1);
/*for (int v = 1; v <= n; ++v)
cerr << v << ": " << ray[v][0] << ' ' << ray[v][1] << ' ' << ray[v][2] << endl;*/
SetUp(1, -1);
#ifdef DEBUG
for (int v = 1; v <= n; ++v)
{
cerr << v << ": " << ray[v][0] << ' ' << ray[v][1] << ' ' << ray[v][2] << endl;
}
for (auto it: ans)
cerr << it << endl;
#endif
if (ans.size())
cout << ans.rbegin()->first << ' ' << ans.rbegin()->second;
else
cout << "0 1";
#ifdef STRESS_TESTING
cout << endl;
AC::Solve(n);
#endif
}
/*
seed: 78587235
1 2
1 3
3 4
4 5
3 6
6 7
4 8
1 9
8 10
8 8 / right answer
*/
Compilation message
road.cpp: In function 'std::pair<int, int> AC::DFS(int, int, int)':
road.cpp:52:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<nei[u].size(); i++)
~^~~~~~~~~~~~~~
road.cpp: In function 'void AC::MaxDist(int)':
road.cpp:75:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<nei[u].size(); i++)
~^~~~~~~~~~~~~~
road.cpp: In function 'void SetUp(int, int)':
road.cpp:172:18: warning: unused variable 'f' [-Wunused-variable]
bool f = (p.first == dists[v][0].first);
^
road.cpp:161:107: warning: 'cnt[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
ans[dists[v][0].first * (dists[v][1].first + dists[v][2].first)] += (delta = (llong)cnt[0] * cnt[1]);
~~~~~^
road.cpp:149:9: warning: 'cnt[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
int cnt[2];
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
