#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
if(x<y)
{
x=y;
return 1;
}
return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
if(x>y)
{
x=y;
return 1;
}
return 0;
}
void online()
{
std::ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef thuc
freopen("input.INP","r",stdin);
freopen("output.OUT","w",stdout);
#else
#endif
}
const ll N=5e5+10,M=1e9+7;
ll par[N],in[N],cnt[N],n,ans,res;
vector<ll> gr[N];
void dfs(ll u)
{
cnt[u]=1;
in[u]=1;
for(auto v:gr[u])
{
if(v==par[u]) continue;
par[v]=u;
dfs(v);
if(maximize(in[u],in[v]+1)) cnt[u]=0;
if(in[u]==in[v]+1)
{
cnt[u]+=cnt[v];
}
}
}
void dp(ll u,ll out,ll outc)
{
vector<pll> vt;
if(u!=1)
vt.emplace_back(out,outc);
for(auto v:gr[u])
{
if(v==par[u]) continue;
vt.emplace_back(in[v],cnt[v]);
}
sort(vt.begin(),vt.end(),greater<pll>());
if(vt.size()>=3&&(vt[0].fi*(vt[1].fi+vt[2].fi))>=res)
{
ll curres=(vt[0].fi*(vt[1].fi+vt[2].fi)),curcnt=0;
ll ba=0;
for(auto v:vt)
{
if(v.fi==vt[2].fi) ba+=v.se;
}
if(vt[1].fi==vt[2].fi)
{
ll cnt=0;
for(auto [x,num]:vt)
{
if(x==vt[1].fi)
{
curcnt+=cnt*num;
cnt+=num;
}
}
}
else if(vt[0].fi==vt[1].fi)
{
curcnt=(vt[0].se+vt[1].se)*ba;
}
else
{
curcnt=vt[1].se*ba;
}
if(maximize(res,curres)) ans=0;
ans+=curcnt;
}
ll mx1=vt[0].fi,mx1c=0,mx2=0,mx2c=1;
if(vt.size()>=2) mx2=vt[1].fi,mx2c=0;
for(auto [v,num]:vt)
{
if(v==mx1) mx1c+=num;
if(v==mx2) mx2c+=num;
}
for(auto v:gr[u])
{
if(v==par[u]) continue;
if(in[v]==mx1)
{
if(cnt[v]==mx1c) dp(v,mx2+1,mx2c);
else dp(v,mx1+1,mx1c-cnt[v]);
}
else dp(v,mx1+1,mx1c);
}
}
int main()
{
online();
cin>>n;
ans=1;
for(int i=1; i<n; i++)
{
ll u,v;
cin>>u>>v;
gr[u].push_back(v);
gr[v].push_back(u);
}
ll flag=1,cnt=0;
for(int i=1;i<=n;i++)
{
if(gr[i].size()>2) flag=0;
if(gr[i].size()==1) cnt++;
}
// if(flag&&cnt==2)
// {
// cout<<"0 1";
// return 0;
// }
dfs(1);
dp(1,0,1);
cout<<res<<' '<<ans<<'\n';
}
Compilation message
road.cpp: In function 'int main()':
road.cpp:134:8: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
134 | ll flag=1,cnt=0;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14936 KB |
Output is correct |
6 |
Correct |
4 ms |
14936 KB |
Output is correct |
7 |
Correct |
3 ms |
14960 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14996 KB |
Output is correct |
11 |
Correct |
3 ms |
15000 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
15004 KB |
Output is correct |
15 |
Correct |
3 ms |
14940 KB |
Output is correct |
16 |
Correct |
3 ms |
15000 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
15000 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
15004 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
3 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14936 KB |
Output is correct |
6 |
Correct |
4 ms |
14936 KB |
Output is correct |
7 |
Correct |
3 ms |
14960 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14996 KB |
Output is correct |
11 |
Correct |
3 ms |
15000 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
15004 KB |
Output is correct |
15 |
Correct |
3 ms |
14940 KB |
Output is correct |
16 |
Correct |
3 ms |
15000 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
15000 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
15004 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
3 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
4 ms |
15452 KB |
Output is correct |
26 |
Correct |
5 ms |
15452 KB |
Output is correct |
27 |
Correct |
5 ms |
15708 KB |
Output is correct |
28 |
Correct |
4 ms |
15708 KB |
Output is correct |
29 |
Correct |
4 ms |
15624 KB |
Output is correct |
30 |
Correct |
4 ms |
15704 KB |
Output is correct |
31 |
Correct |
4 ms |
15628 KB |
Output is correct |
32 |
Correct |
4 ms |
15452 KB |
Output is correct |
33 |
Correct |
5 ms |
15524 KB |
Output is correct |
34 |
Correct |
4 ms |
15704 KB |
Output is correct |
35 |
Correct |
4 ms |
15708 KB |
Output is correct |
36 |
Correct |
5 ms |
15452 KB |
Output is correct |
37 |
Correct |
6 ms |
15708 KB |
Output is correct |
38 |
Correct |
5 ms |
15964 KB |
Output is correct |
39 |
Correct |
6 ms |
15456 KB |
Output is correct |
40 |
Correct |
4 ms |
15196 KB |
Output is correct |
41 |
Correct |
5 ms |
15196 KB |
Output is correct |
42 |
Correct |
5 ms |
15196 KB |
Output is correct |
43 |
Correct |
5 ms |
15204 KB |
Output is correct |
44 |
Correct |
4 ms |
15196 KB |
Output is correct |
45 |
Correct |
4 ms |
15208 KB |
Output is correct |
46 |
Correct |
4 ms |
15196 KB |
Output is correct |
47 |
Correct |
4 ms |
15196 KB |
Output is correct |
48 |
Correct |
4 ms |
15452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14936 KB |
Output is correct |
6 |
Correct |
4 ms |
14936 KB |
Output is correct |
7 |
Correct |
3 ms |
14960 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14996 KB |
Output is correct |
11 |
Correct |
3 ms |
15000 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
15004 KB |
Output is correct |
15 |
Correct |
3 ms |
14940 KB |
Output is correct |
16 |
Correct |
3 ms |
15000 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
15000 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
15004 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
3 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
4 ms |
15452 KB |
Output is correct |
26 |
Correct |
5 ms |
15452 KB |
Output is correct |
27 |
Correct |
5 ms |
15708 KB |
Output is correct |
28 |
Correct |
4 ms |
15708 KB |
Output is correct |
29 |
Correct |
4 ms |
15624 KB |
Output is correct |
30 |
Correct |
4 ms |
15704 KB |
Output is correct |
31 |
Correct |
4 ms |
15628 KB |
Output is correct |
32 |
Correct |
4 ms |
15452 KB |
Output is correct |
33 |
Correct |
5 ms |
15524 KB |
Output is correct |
34 |
Correct |
4 ms |
15704 KB |
Output is correct |
35 |
Correct |
4 ms |
15708 KB |
Output is correct |
36 |
Correct |
5 ms |
15452 KB |
Output is correct |
37 |
Correct |
6 ms |
15708 KB |
Output is correct |
38 |
Correct |
5 ms |
15964 KB |
Output is correct |
39 |
Correct |
6 ms |
15456 KB |
Output is correct |
40 |
Correct |
4 ms |
15196 KB |
Output is correct |
41 |
Correct |
5 ms |
15196 KB |
Output is correct |
42 |
Correct |
5 ms |
15196 KB |
Output is correct |
43 |
Correct |
5 ms |
15204 KB |
Output is correct |
44 |
Correct |
4 ms |
15196 KB |
Output is correct |
45 |
Correct |
4 ms |
15208 KB |
Output is correct |
46 |
Correct |
4 ms |
15196 KB |
Output is correct |
47 |
Correct |
4 ms |
15196 KB |
Output is correct |
48 |
Correct |
4 ms |
15452 KB |
Output is correct |
49 |
Correct |
420 ms |
82848 KB |
Output is correct |
50 |
Correct |
386 ms |
89424 KB |
Output is correct |
51 |
Correct |
393 ms |
95016 KB |
Output is correct |
52 |
Correct |
396 ms |
75084 KB |
Output is correct |
53 |
Correct |
363 ms |
95052 KB |
Output is correct |
54 |
Correct |
336 ms |
102316 KB |
Output is correct |
55 |
Correct |
407 ms |
84636 KB |
Output is correct |
56 |
Correct |
346 ms |
92444 KB |
Output is correct |
57 |
Correct |
381 ms |
97860 KB |
Output is correct |
58 |
Correct |
373 ms |
90352 KB |
Output is correct |
59 |
Correct |
366 ms |
90404 KB |
Output is correct |
60 |
Correct |
409 ms |
86964 KB |
Output is correct |
61 |
Correct |
579 ms |
139888 KB |
Output is correct |
62 |
Correct |
624 ms |
123228 KB |
Output is correct |
63 |
Correct |
596 ms |
73388 KB |
Output is correct |
64 |
Correct |
563 ms |
61988 KB |
Output is correct |
65 |
Correct |
577 ms |
54200 KB |
Output is correct |
66 |
Correct |
519 ms |
50256 KB |
Output is correct |
67 |
Correct |
569 ms |
48156 KB |
Output is correct |
68 |
Correct |
511 ms |
47288 KB |
Output is correct |
69 |
Correct |
502 ms |
46928 KB |
Output is correct |
70 |
Correct |
508 ms |
46760 KB |
Output is correct |
71 |
Correct |
488 ms |
46696 KB |
Output is correct |
72 |
Correct |
496 ms |
46728 KB |
Output is correct |
73 |
Correct |
489 ms |
47092 KB |
Output is correct |
74 |
Correct |
507 ms |
47920 KB |
Output is correct |
75 |
Correct |
510 ms |
48676 KB |
Output is correct |
76 |
Correct |
446 ms |
49608 KB |
Output is correct |
77 |
Correct |
375 ms |
53824 KB |
Output is correct |
78 |
Correct |
258 ms |
60884 KB |
Output is correct |