#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
int n, maxx[maxn], cnt[maxn];
vi ke[maxn];
pii ans;
void dfs(int u, int par = 0)
{
maxx[u] = 0;
cnt[u] = 1;
for (int v : ke[u])
if (v != par)
{
dfs(v, u);
if (maxx[u] < maxx[v] + 1)
{
maxx[u] = maxx[v] + 1;
cnt[u] = cnt[v];
}
else if (maxx[u] == maxx[v] + 1)
cnt[u] += cnt[v];
}
}
void dfs2(int u, pii par_dist, int par)
{
vii path;
if (u > 1 or ke[u].size() == 1)
path.pb(par_dist);
for (int v : ke[u])
if (v != par)
path.pb(maxx[v] + 1, cnt[v]);
sort(path.begin(), path.end(), greater<pii>());
if (path.size() > 2)
{
int a = path[0].fi;
int b = path[1].fi;
int c = path[2].fi;
int fre = 0;
int tot = 0;
int longest_route = a * (b + c);
// a >= b >= c => a * (b + c) >= b * (c + a) , a * (b + c) >= c * (a + b)
for (auto [len, dem] : path)
if (len == c)
tot += dem;
if (a != b and b != c)
fre = tot * path[1].se;
else if (a == b and b == c)
{
// tot = (x + y + z + ...)
fre = tot * tot; // = (x + y + z + ...) ^ 2
for (auto [len, dem] : path)
if (len == a)
fre -= dem * dem;
fre /= 2; // = xy + yz + zx + ...
}
else if (a == b and b != c)
fre = (path[0].se + path[1].se) * tot;
else if (a != b and b == c)
{
fre = tot * tot;
for (auto [len, dem] : path)
if (len == c)
fre -= dem * dem;
fre /= 2;
}
// cout << longest_route << "\n";
if (ans.fi < longest_route)
ans = {longest_route, fre};
else if (ans.fi == longest_route)
ans.se += fre;
}
// cout << u << ' ' << ans.fi << ' ' << ans.se << "\n";
pii longest1 = {0, 0};
pii longest2 = {0, 0};
for(auto [len,dem] : path)
{
if (len + 1 > longest1.fi)
{
swap(longest1, longest2);
longest1 = {len + 1, dem};
}
else if(len + 1 == longest1.fi) longest1.se += dem;
else if(len + 1 > longest2.fi) longest2 = {len + 1,dem};
else if(len + 1 == longest2.fi) longest2.se += dem;
}
for (int v : ke[u])
if (v != par)
{
if (maxx[v] + 2 == longest1.fi)
{
if (cnt[v] == longest1.se)
dfs2(v, longest2, u);
else
dfs2(v, {longest1.fi, longest1.se - cnt[v]}, u);
}
else
dfs2(v, longest1, u);
}
}
main()
{
#define name "TASK"
if (fopen(name ".inp", "r"))
{
freopen(name ".inp", "r", stdin);
freopen(name ".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
fo(i, 1, n - 1)
{
int u, v;
cin >> u >> v;
ke[u].pb(v);
ke[v].pb(u);
}
dfs(1);
dfs2(1, {0, 1}, 1);
cout << ans.fi << ' ' << ans.se;
}
Compilation message
road.cpp:138:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
138 | main()
| ^~~~
road.cpp: In function 'int main()':
road.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | freopen(name ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | freopen(name ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 2 |
Correct |
4 ms |
27228 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
27308 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 2 |
Correct |
4 ms |
27228 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
27308 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 2 |
Correct |
4 ms |
27228 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
27308 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
