#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9
using namespace std;
typedef long long ll;
int n;
ll mx = 0;
ll ct = 0;
vector<int> v[500002];
int dist[500002], mxn[500002];
void dfs(int dad, int nod)
{
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(vecin == dad)
continue;
dfs(nod, vecin);
dist[nod] = max(dist[nod], dist[vecin] + 1);
}
}
void dfs2(int dad, int nod, int mx)
{
mxn[nod] = mx;
int mxx = 0, mxx2 = 0;
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(vecin == dad)
continue;
if(dist[vecin] + 1 > mxx)
mxx2 = mxx, mxx = dist[vecin] + 1;
else
if(dist[vecin] + 1 > mxx2)
mxx2 = dist[vecin] + 1;
}
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(vecin == dad)
continue;
if(dist[vecin] + 1 == mxx)
{
if(mx != 0)
dfs2(nod, vecin, max(mx + 1, mxx2 + 1));
else
dfs2(nod, vecin, mxx2 + 1);
}
else
{
if(mx != 0)
dfs2(nod, vecin, max(mx + 1, mxx + 1));
else
dfs2(nod, vecin, mxx + 1);
}
}
}
pair<int, int> dp[500002];
void dfsdp(int dad, int nod)
{
if(v[nod].size() == 1)
{
dp[nod] = {0, 0};
return;
}
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(vecin == dad)
continue;
dfsdp(nod, vecin);
}
int mxothr = 0;
int wh = 0;
int cot = 0;
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(vecin == dad)
continue;
if(dp[vecin].fi + 1 > dp[nod].fi)
wh = i, dp[nod] = dp[vecin], dp[nod].fi++, cot = 1;
else
if(dp[vecin].fi + 1 == dp[nod].fi && dp[vecin].se > dp[nod].se)
wh = i, dp[nod] = dp[vecin], dp[nod].fi++, ++cot;
}
if(mxn[nod] >= dist[nod])
{
if(cot >= 2)
{
if(2LL * dp[nod].fi * mxn[nod] > mx)
mx = 2 * dp[nod].fi, ct = 1LL * cot * (cot - 1) / 2;
else
if(2LL * mxn[nod] * dp[nod].fi == mx)
ct += 1LL * cot * (cot - 1) / 2;
}
else
{
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(vecin == dad)
continue;
if(i != wh)
{
if(1LL * mxn[nod] * (dp[nod].fi + dp[vecin].fi + 1) > mx)
mx = 1LL * mxn[nod] * (dp[nod].fi + dp[vecin].fi + 1), ct = 1;
else
if(1LL * mxn[nod] * (dp[nod].fi + dp[vecin].fi + 1) == mx)
++ct;
}
}
}
}
else
{
vector<pair<int, int> >vx;
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(vecin == dad)
continue;
vx.pb({dp[vecin].fi + 1, dp[vecin].se});
// cout << dp[vecin].fi + 1 << " " << dp[vecin].se << '\n';
}
sort(vx.begin(), vx.end());
for(int j = vx.size() - 1; j >= 0; )
{
bool rau = 0;
if(j != vx.size() - 1)
rau = 1;
int i = j;
while(i >= 0 && vx[j] == vx[i])
--i;
ll countt = j - i;
// cout << vx[j].fi << " " << vx[j].se << " " << countt << '\n';
if(countt >= 2)
{
if(j == vx.size() - 1)
{
ll di = 2LL * vx[j].fi;
if(countt == 2)
if(i >= 0)
di = di * max(mxn[nod], max(vx[i].fi, vx[j].se));
else
di = di * max(mxn[nod], vx[j].se);
else
di = di * vx[j].fi;
if(di > mx)
mx = di, ct = 1LL * countt * (countt - 1) / 2;
else
if(di == mx)
ct += 1LL * countt * (countt - 1) / 2;
}
else
{
ll di = 2LL * vx[j].fi * max(mxn[nod], vx.back().fi);
if(di > mx)
mx = di, ct = 1LL * countt * (countt - 1) / 2;
else
if(di == mx)
ct += 1LL * countt * (countt - 1) / 2;
}
}
else
{
for(int pp = j - 1; pp >= 0; --pp)
{
ll dist = vx[j].fi + vx[pp].fi;
if(j != vx.size() - 1)
dist = dist * vx.back().fi;
else
if(pp == j-1)
{
if(pp == 0)
dist = dist * max(max(vx[j].se, vx[pp].se), mxn[nod]);
else
dist = dist * max(max(vx[j].se, vx[pp].se), max(mxn[nod], vx[j - 1].fi));
}
}
}
j = i;
if(rau)
break;
}
}
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(vecin == dad)
continue;
if(i != wh)
dp[nod].se = max(dp[nod].se, dp[vecin].fi + 1);
else
dp[nod].se = max(dp[nod].se, dp[vecin].se);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
int nL = 0;
for(int i = 1; i < n; ++i)
{
int a, b;
cin >> a >> b;
v[a].pb(b);
v[b].pb(a);
}
for(int i = 1; i <= n; ++i)
if(v[i].size() == 1)
++nL;
if(nL == 2)
{
cout << 0 << " " << 1;
return 0;
}
int root = 0;
for(int i = 1; i <= n; ++i)
if(v[i].size() != 1)
{
root = i;
break;
}
dfs(0, root);
dfs2(0, root, 0);
dfsdp(0, root);
cout << mx << " " << ct << '\n';
return 0;
}
Compilation message
road.cpp: In function 'void dfs(int, int)':
road.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
road.cpp: In function 'void dfs2(int, int, int)':
road.cpp:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
road.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
road.cpp: In function 'void dfsdp(int, int)':
road.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
road.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
road.cpp:109:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
road.cpp:128:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
road.cpp:140:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j != vx.size() - 1)
~~^~~~~~~~~~~~~~~~
road.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j == vx.size() - 1)
~~^~~~~~~~~~~~~~~~
road.cpp:180:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j != vx.size() - 1)
~~^~~~~~~~~~~~~~~~
road.cpp:197:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
road.cpp:83:9: warning: unused variable 'mxothr' [-Wunused-variable]
int mxothr = 0;
^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
12024 KB |
Output is correct |
| 2 |
Correct |
13 ms |
12024 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12156 KB |
Output is correct |
| 6 |
Correct |
12 ms |
12024 KB |
Output is correct |
| 7 |
Incorrect |
12 ms |
12152 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
12024 KB |
Output is correct |
| 2 |
Correct |
13 ms |
12024 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12156 KB |
Output is correct |
| 6 |
Correct |
12 ms |
12024 KB |
Output is correct |
| 7 |
Incorrect |
12 ms |
12152 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
12024 KB |
Output is correct |
| 2 |
Correct |
13 ms |
12024 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12156 KB |
Output is correct |
| 6 |
Correct |
12 ms |
12024 KB |
Output is correct |
| 7 |
Incorrect |
12 ms |
12152 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
