#include <bits/stdc++.h>
#define MAXN 500007
using namespace std;
vector<int> g[MAXN];
int b,mb,u,v;
long long pot,cnt,d[MAXN],k[MAXN],ds[2][MAXN];
void dfsD(int s,int f,int di)
{
d[s]=di;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsD(g[s][i],s,di+1);
}
void dfsd(int s,int f,int ka,int di)
{
ds[ka][s]=di;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsD(g[s][i],s,di+1);
}
int dfsp(int s,int f)
{
int mx=0;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) mx=max(mx,dfsp(g[s][i],s));
d[s]=mx+1;
return d[s];
}
void calc(int s,int f,long long mx,long long du)
{
if(s!=f && g[s].size()==1)
{
if(s!=mb && du*mx==pot) cnt++;
if(s!=mb && du*mx>pot) {pot=du*mx; cnt=1;}
return;
}
int mxi=0;
long long mx1=0,mx2=0;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
calc(g[s][mxi],s,max(mx,mx2),du+1);
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && i!=mxi) calc(g[s][i],s,max(mx,mx1),du+1);
}
void dfs(int s,int f,long long du,int ka)
{
if(s==v || s==u) {d[s]=-MAXN; return;}
if(g[s].size()==1 && s!=f) {k[s]=1; d[s]=1; return;}
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s,du+1,ka);
int mxi=0;
long long mx1=0,mx2=0;
k[s]=0;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) k[s]+=k[g[s][i]];
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
d[s]=mx1+1;
long long tc=0;
if(mx1==mx2)
{
tc=k[s]*k[s];
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) tc-=k[g[s][i]]*k[g[s][i]];
tc/=2;
}
else
{
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx2) tc+=k[g[s][i]];
tc*=k[s];
}
if(mx2==0 || (ka==1 && ds[0][s]==ds[1][s])) return;
if((mx1+mx2)*du>pot) {pot=(mx1+mx2)*du; cnt=0;}
if((mx1+mx2)*du==pot) cnt+=tc;
}
int main()
{
int n;
u=1; v=1;
scanf("%d",&n);
for(int i=0;i<n-1;i++)
{
int t1,t2;
scanf("%d%d",&t1,&t2);
g[t1].push_back(t2);
g[t2].push_back(t1);
}
dfsD(1,1,0);
for(int i=1;i<=n;i++) if(d[i]>d[u]) u=i;
dfsD(u,u,0);
for(int i=1;i<=n;i++) if(d[i]>d[v]) v=i;
dfsd(u,u,0,0);
dfsd(v,v,1,0);
dfsp(u,u);
calc(u,u,0,0);
mb=u;
dfsp(v,v);
calc(v,v,0,0);
dfs(u,u,0,0);
dfs(v,v,0,1);
printf("%lld %lld",pot,cnt);
}
Compilation message
road.cpp: In function 'void dfsD(int, int, int)':
road.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsD(g[s][i],s,di+1);
~^~~~~~~~~~~~
road.cpp: In function 'void dfsd(int, int, int, int)':
road.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsD(g[s][i],s,di+1);
~^~~~~~~~~~~~
road.cpp: In function 'int dfsp(int, int)':
road.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) mx=max(mx,dfsp(g[s][i],s));
~^~~~~~~~~~~~
road.cpp: In function 'void calc(int, int, long long int, long long int)':
road.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
~^~~~~~~~~~~~
road.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
~^~~~~~~~~~~~
road.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && i!=mxi) calc(g[s][i],s,max(mx,mx1),du+1);
~^~~~~~~~~~~~
road.cpp: In function 'void dfs(int, int, long long int, int)':
road.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s,du+1,ka);
~^~~~~~~~~~~~
road.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
~^~~~~~~~~~~~
road.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) k[s]+=k[g[s][i]];
~^~~~~~~~~~~~
road.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
~^~~~~~~~~~~~
road.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) tc-=k[g[s][i]]*k[g[s][i]];
~^~~~~~~~~~~~
road.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx2) tc+=k[g[s][i]];
~^~~~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
road.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&t1,&t2);
~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
12152 KB |
Output is correct |
| 2 |
Correct |
16 ms |
12152 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12296 KB |
Output is correct |
| 4 |
Correct |
15 ms |
12296 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12296 KB |
Output is correct |
| 6 |
Correct |
16 ms |
12296 KB |
Output is correct |
| 7 |
Incorrect |
16 ms |
12296 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
12152 KB |
Output is correct |
| 2 |
Correct |
16 ms |
12152 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12296 KB |
Output is correct |
| 4 |
Correct |
15 ms |
12296 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12296 KB |
Output is correct |
| 6 |
Correct |
16 ms |
12296 KB |
Output is correct |
| 7 |
Incorrect |
16 ms |
12296 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
12152 KB |
Output is correct |
| 2 |
Correct |
16 ms |
12152 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12296 KB |
Output is correct |
| 4 |
Correct |
15 ms |
12296 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12296 KB |
Output is correct |
| 6 |
Correct |
16 ms |
12296 KB |
Output is correct |
| 7 |
Incorrect |
16 ms |
12296 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
