#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
typedef long long llong;
const int maxN = 500005;
vector<int> nei[maxN];
pair<int, int> ray[maxN][3];
map<llong, llong> ans;
vector<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 << "}";
}
inline const pair<int, int>& Second(const pair<int, int>* a)
{
return a[0].second >= 2 ? a[0] : a[1];
}
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;
Maximize(ray[v], {val = ray[to][0].first + 1, ray[to][0].second/*1*/});
dists[v].push_back(val);
}
}
void SetUp(int v, int par)
{
for (int to: nei[v])
if (to != par)
{
// Set up[to].
int val = 0;
if (ray[v][0].first == ray[to][0].first + 1 && ray[v][0].second == ray[to][0].second)
Maximize(ray[to], {val = Second(ray[v]).first + 1, Second(ray[v]).second/*1*/});
else if (ray[v][0].first == ray[to][0].first + 1)
Maximize(ray[to], {val = ray[v][0].first + 1, ray[v][0].second - ray[to][0].second/*1*/});
else
Maximize(ray[to], {val = ray[v][0].first + 1, ray[v][0].second});
dists[to].push_back(val);
SetUp(to, v);
}
if (dists[v].size() < 3) return;
sort(dists[v].begin(), dists[v].end(), greater<int>());
bool eq = (dists[v][1] == dists[v][2]);
if (v == 1)
cerr << "dists: " << dists[v][0] << ' ' << dists[v][1] << ' ' << dists[v][2] << endl;
int cnt[2];
for (int i = 0; i < 3; ++i)
{
if (ray[v][i].first == dists[v][1])
cnt[0] = ray[v][i].second;
if (ray[v][i].first == dists[v][2])
cnt[1] = ray[v][i].second;
}
if (eq)
ans[dists[v][0] * (dists[v][1] + dists[v][2])] += (cnt[0] * (cnt[0] - 1)) / 2;
else
ans[dists[v][0] * (dists[v][1] + dists[v][2])] += cnt[0] * cnt[1];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
// cin >> n;
// n = rand() % 20 + 1;
cin >> n;
/*int seed;
cin >> seed;
srand(seed);
cerr << n << endl;*/
for (int i = 1; i < n; ++i)
{
int u, v;
cin >> u >> v;
/*v = i + 1;
u = rand() % i + 1;
cerr << u << ' ' << v << endl;*/
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);
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;*/
if (ans.size())
cout << ans.rbegin()->first << ' ' << ans.rbegin()->second;
else
cout << "0 1";
// cout << endl;
// AC::Solve(n);
}
/*
8
1 2
1 3
1 4
2 5
4 6
1 7
2 8
6 5
6 7 // right answer
*/
Compilation message
road.cpp: In function 'std::pair<int, int> AC::DFS(int, int, int)':
road.cpp:46: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:69: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:154:66: warning: 'cnt[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
ans[dists[v][0] * (dists[v][1] + dists[v][2])] += cnt[0] * cnt[1];
~~~~~~~^~~~~~~~
road.cpp:154:66: warning: 'cnt[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
