// #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?
{
#ifdef DEBUG
if (v == 3)
{
cerr << "Good.\tp = " << p << endl;
}
#endif
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 = 27;
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:174: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];
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
23800 KB |
Output is correct |
2 |
Correct |
23 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
23800 KB |
Output is correct |
4 |
Correct |
23 ms |
23804 KB |
Output is correct |
5 |
Correct |
23 ms |
23800 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
23 ms |
23772 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23800 KB |
Output is correct |
10 |
Correct |
23 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23788 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
23 ms |
23800 KB |
Output is correct |
15 |
Correct |
24 ms |
23884 KB |
Output is correct |
16 |
Correct |
24 ms |
23796 KB |
Output is correct |
17 |
Correct |
23 ms |
23800 KB |
Output is correct |
18 |
Correct |
23 ms |
23804 KB |
Output is correct |
19 |
Correct |
23 ms |
23928 KB |
Output is correct |
20 |
Correct |
23 ms |
23928 KB |
Output is correct |
21 |
Correct |
23 ms |
23792 KB |
Output is correct |
22 |
Correct |
23 ms |
23800 KB |
Output is correct |
23 |
Correct |
23 ms |
23872 KB |
Output is correct |
24 |
Correct |
23 ms |
23800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
23800 KB |
Output is correct |
2 |
Correct |
23 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
23800 KB |
Output is correct |
4 |
Correct |
23 ms |
23804 KB |
Output is correct |
5 |
Correct |
23 ms |
23800 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
23 ms |
23772 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23800 KB |
Output is correct |
10 |
Correct |
23 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23788 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
23 ms |
23800 KB |
Output is correct |
15 |
Correct |
24 ms |
23884 KB |
Output is correct |
16 |
Correct |
24 ms |
23796 KB |
Output is correct |
17 |
Correct |
23 ms |
23800 KB |
Output is correct |
18 |
Correct |
23 ms |
23804 KB |
Output is correct |
19 |
Correct |
23 ms |
23928 KB |
Output is correct |
20 |
Correct |
23 ms |
23928 KB |
Output is correct |
21 |
Correct |
23 ms |
23792 KB |
Output is correct |
22 |
Correct |
23 ms |
23800 KB |
Output is correct |
23 |
Correct |
23 ms |
23872 KB |
Output is correct |
24 |
Correct |
23 ms |
23800 KB |
Output is correct |
25 |
Correct |
27 ms |
24444 KB |
Output is correct |
26 |
Correct |
27 ms |
24624 KB |
Output is correct |
27 |
Correct |
27 ms |
24660 KB |
Output is correct |
28 |
Correct |
27 ms |
24568 KB |
Output is correct |
29 |
Correct |
28 ms |
24696 KB |
Output is correct |
30 |
Correct |
27 ms |
24696 KB |
Output is correct |
31 |
Correct |
28 ms |
24696 KB |
Output is correct |
32 |
Correct |
27 ms |
24668 KB |
Output is correct |
33 |
Correct |
27 ms |
24568 KB |
Output is correct |
34 |
Correct |
27 ms |
24568 KB |
Output is correct |
35 |
Correct |
27 ms |
24568 KB |
Output is correct |
36 |
Correct |
28 ms |
24696 KB |
Output is correct |
37 |
Correct |
27 ms |
24696 KB |
Output is correct |
38 |
Correct |
28 ms |
24824 KB |
Output is correct |
39 |
Correct |
27 ms |
24568 KB |
Output is correct |
40 |
Correct |
27 ms |
24440 KB |
Output is correct |
41 |
Correct |
27 ms |
24312 KB |
Output is correct |
42 |
Correct |
27 ms |
24440 KB |
Output is correct |
43 |
Correct |
27 ms |
24312 KB |
Output is correct |
44 |
Correct |
27 ms |
24312 KB |
Output is correct |
45 |
Correct |
26 ms |
24312 KB |
Output is correct |
46 |
Correct |
26 ms |
24184 KB |
Output is correct |
47 |
Correct |
26 ms |
24312 KB |
Output is correct |
48 |
Correct |
26 ms |
24440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
23800 KB |
Output is correct |
2 |
Correct |
23 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
23800 KB |
Output is correct |
4 |
Correct |
23 ms |
23804 KB |
Output is correct |
5 |
Correct |
23 ms |
23800 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
23 ms |
23772 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23800 KB |
Output is correct |
10 |
Correct |
23 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23788 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
23 ms |
23800 KB |
Output is correct |
15 |
Correct |
24 ms |
23884 KB |
Output is correct |
16 |
Correct |
24 ms |
23796 KB |
Output is correct |
17 |
Correct |
23 ms |
23800 KB |
Output is correct |
18 |
Correct |
23 ms |
23804 KB |
Output is correct |
19 |
Correct |
23 ms |
23928 KB |
Output is correct |
20 |
Correct |
23 ms |
23928 KB |
Output is correct |
21 |
Correct |
23 ms |
23792 KB |
Output is correct |
22 |
Correct |
23 ms |
23800 KB |
Output is correct |
23 |
Correct |
23 ms |
23872 KB |
Output is correct |
24 |
Correct |
23 ms |
23800 KB |
Output is correct |
25 |
Correct |
27 ms |
24444 KB |
Output is correct |
26 |
Correct |
27 ms |
24624 KB |
Output is correct |
27 |
Correct |
27 ms |
24660 KB |
Output is correct |
28 |
Correct |
27 ms |
24568 KB |
Output is correct |
29 |
Correct |
28 ms |
24696 KB |
Output is correct |
30 |
Correct |
27 ms |
24696 KB |
Output is correct |
31 |
Correct |
28 ms |
24696 KB |
Output is correct |
32 |
Correct |
27 ms |
24668 KB |
Output is correct |
33 |
Correct |
27 ms |
24568 KB |
Output is correct |
34 |
Correct |
27 ms |
24568 KB |
Output is correct |
35 |
Correct |
27 ms |
24568 KB |
Output is correct |
36 |
Correct |
28 ms |
24696 KB |
Output is correct |
37 |
Correct |
27 ms |
24696 KB |
Output is correct |
38 |
Correct |
28 ms |
24824 KB |
Output is correct |
39 |
Correct |
27 ms |
24568 KB |
Output is correct |
40 |
Correct |
27 ms |
24440 KB |
Output is correct |
41 |
Correct |
27 ms |
24312 KB |
Output is correct |
42 |
Correct |
27 ms |
24440 KB |
Output is correct |
43 |
Correct |
27 ms |
24312 KB |
Output is correct |
44 |
Correct |
27 ms |
24312 KB |
Output is correct |
45 |
Correct |
26 ms |
24312 KB |
Output is correct |
46 |
Correct |
26 ms |
24184 KB |
Output is correct |
47 |
Correct |
26 ms |
24312 KB |
Output is correct |
48 |
Correct |
26 ms |
24440 KB |
Output is correct |
49 |
Correct |
837 ms |
94704 KB |
Output is correct |
50 |
Correct |
885 ms |
99376 KB |
Output is correct |
51 |
Correct |
853 ms |
103092 KB |
Output is correct |
52 |
Correct |
856 ms |
91448 KB |
Output is correct |
53 |
Incorrect |
866 ms |
107896 KB |
Output isn't correct |
54 |
Halted |
0 ms |
0 KB |
- |