#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;
typedef long long LL;
typedef double ld;
/*
考虑如何计算出互相可达的点对数量吧
情况实在太过复杂了啊
qewss`
//题解nmb
//问题是我60分都不会啊
点对除了使用lca计算以外还有什么办法?
与每个点连通的点的数量。。
f1[i][j] 表示以点i为根,在i的祖先中点i能够到达的点的数量为j的最优值
f2[i][j] 表示以点i为根,在i的子孙中能够到达的点的数量为j的最优值
f1[i][j] 的计算貌似可以dp啊
若枚举点i能够到达的连通块。。
这个算法是n^3的,稍微靠谱点,但还是不是n^2的
思路依旧是对于点i,得知其能到达的点的个数。。
由于在原来的转移中对于f1的转移为O(1)。。。
难道还是要使用LCA么。。
我觉得肯定不行啊。。
所以说还是结论题:
一定是有一个中心,mb如果知道这个了的话这题还有毛意思啊。。
sum=a+b+c+d
ab+bc+cd<max( (a+b)*(c+d), (sum-a)*a,(sum-b)*b,(sum-c)*c,(sum-d)*d)
擦。。。
枚举中心点可秒啊。。
可以得到各种各样的东东。。
但是这样还是不会优化到N \sqrt(N)
肯定是选择重心作为根。。我真tm是傻逼。。
*/
const int MAX=500000+10;
int n;
int begin[MAX],t[MAX],next[MAX],tot;
int hash[MAX],size[MAX],q[MAX];
LL dist[MAX],distp[MAX];
void add(int a,int b)
{
t[++tot]=b;
next[tot]=begin[a];
begin[a]=tot;
}
int could[MAX];
int f[MAX],num[MAX],f1[MAX];
LL work(int u)
{
int i,top=0;
LL ans=0;
for(i=begin[u];i;i=next[i])
{
int v=t[i];
if(hash[v]==u)
{
ans+=dist[v]+size[v];
could[++top]=size[v];
}
else
{
ans+=distp[u];
could[++top]=n-size[u];
}
}
REP(i,1,top)
if(could[i]*2>=n-1)
return ans+LL(n-1-could[i])*could[i];
int T=sqrt(n)+1;
REP(i,1,T)
num[i]=0;
memset(f,0,sizeof f);
f[0]=1;
int half=(n+1)/2;
REP(i,1,top)
if(could[i]<=T)
num[could[i]]++;
else
for(int j=half;j>=could[i];--j)
f[j]|=f[j-could[i]];
REP(i,1,T)
{
if(!num[i])
continue;
int j;
REP(j,0,half)
f1[j]=0;
REP(j,0,i-1)
{
int sum=0;
for(int k=0;k*i+j<=half;++k)
{
sum+=f[k*i+j];
f1[k*i+j]=(sum>0);
if(k>=num[i])
sum-=f[(k-num[i])*i+j];
}
}
REP(j,0,half)
f[j]=f1[j];
}
LL t=0;
REP(i,0,half)
if(f[i])
t=max(t,ans+i*LL(n-1-i));
return t;
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,j;
scanf("%d",&n);
REP(i,1,n-1)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
int head=1,end=1;
q[end++]=1;
hash[1]=-1;
while(head<end)
{
int u=q[head++];
for(i=begin[u];i;i=next[i])
{
int v=t[i];
if(!hash[v])
{
q[end++]=v;
hash[v]=u;
}
}
}
for(int i=n;i>=1;--i)
{
int u=q[i];
size[u]=1;
for(int j=begin[u];j;j=next[j])
{
int v=t[j];
if(hash[v]!=u)
continue;
dist[u]+=dist[v]+size[v];
size[u]+=size[v];
}
}
distp[1]=0;
REP(i,1,n)
{
int u=q[i];
for(j=begin[u];j;j=next[j])
{
int v=t[j];
if(hash[v]!=u)
continue;
distp[v]=dist[u]+distp[u]-(dist[v]+size[v])+(n-size[v]);
}
}
LL ans=0;
REP(i,1,n)
ans=max( ans, work(i) ) ;
cout<<n-1<<" "<<ans<<endl;
return 0;
}
I2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxjc3RkbGliPgojaW5jbHVkZTxjc3RyaW5nPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPGlvc3RyZWFtPgojaW5jbHVkZTxmc3RyZWFtPgojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPGN0aW1lPgojaW5jbHVkZTxzZXQ+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxjbWF0aD4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxiaXRzZXQ+CiNpbmNsdWRlPGZ1bmN0aW9uYWw+CiNkZWZpbmUgeCBmaXJzdAojZGVmaW5lIHkgc2Vjb25kCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgUkVQKGksbCxyKSBmb3IoKGkpPShsKTsoaSk8PShyKTsrKyhpKSkKI2RlZmluZSBSRVAyKGksbCxyKSBmb3IoKGkpPShsKTsoaSkhPShyKTsrKyhpKSkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgbG9uZyBsb25nIExMOwp0eXBlZGVmIGRvdWJsZSBsZDsKCi8qCiAgIOiAg+iZkeWmguS9leiuoeeul+WHuuS6kuebuOWPr+i+vueahOeCueWvueaVsOmHj+WQpwogICDmg4XlhrXlrp7lnKjlpKrov4flpI3mnYLkuobllYoKcWV3c3NgCiAgIC8v6aKY6Kejbm1iCiAgIC8v6Zeu6aKY5piv5oiRNjDliIbpg73kuI3kvJrllYoKCiAgIOeCueWvuemZpOS6huS9v+eUqGxjYeiuoeeul+S7peWklui/mOacieS7gOS5iOWKnuazle+8nwoKICAg5LiO5q+P5Liq54K56L+e6YCa55qE54K555qE5pWw6YeP44CC44CCCiAgIGYxW2ldW2pdIOihqOekuuS7peeCuWnkuLrmoLnvvIzlnKhp55qE56WW5YWI5Lit54K5aeiDveWkn+WIsOi+vueahOeCueeahOaVsOmHj+S4umrnmoTmnIDkvJjlgLwKICAgZjJbaV1bal0g6KGo56S65Lul54K5aeS4uuague+8jOWcqGnnmoTlrZDlrZnkuK3og73lpJ/liLDovr7nmoTngrnnmoTmlbDph4/kuLpq55qE5pyA5LyY5YC8CgogICBmMVtpXVtqXSDnmoTorqHnrpfosozkvLzlj6/ku6VkcOWVigogICDoi6XmnprkuL7ngrlp6IO95aSf5Yiw6L6+55qE6L+e6YCa5Z2X44CC44CCCgogICDov5nkuKrnrpfms5XmmK9uXjPnmoTvvIznqI3lvq7pnaDosLHngrnvvIzkvYbov5jmmK/kuI3mmK9uXjLnmoQKCiAgIOaAnei3r+S+neaXp+aYr+WvueS6jueCuWnvvIzlvpfnn6Xlhbbog73liLDovr7nmoTngrnnmoTkuKrmlbDjgILjgIIKICAg55Sx5LqO5Zyo5Y6f5p2l55qE6L2s56e75Lit5a+55LqOZjHnmoTovaznp7vkuLpPKDEp44CC44CC44CCCgogICDpmr7pgZPov5jmmK/opoHkvb/nlKhMQ0HkuYjjgILjgIIKICAg5oiR6KeJ5b6X6IKv5a6a5LiN6KGM5ZWK44CC44CCCgogICDmiYDku6Xor7Tov5jmmK/nu5PorrrpopjvvJoKICAg5LiA5a6a5piv5pyJ5LiA5Liq5Lit5b+D77yMbWLlpoLmnpznn6XpgZPov5nkuKrkuobnmoTor53ov5npopjov5jmnInmr5vmhI/mgJ3llYrjgILjgIIKCiAgIHN1bT1hK2IrYytkCiAgIGFiK2JjK2NkPG1heCggKGErYikqKGMrZCksIChzdW0tYSkqYSwoc3VtLWIpKmIsKHN1bS1jKSpjLChzdW0tZCkqZCkKICAg5pOm44CC44CC44CCCgogICDmnprkuL7kuK3lv4Pngrnlj6/np5LllYrjgILjgIIKICAg5Y+v5Lul5b6X5Yiw5ZCE56eN5ZCE5qC355qE5Lic5Lic44CC44CCCgogICDkvYbmmK/ov5nmoLfov5jmmK/kuI3kvJrkvJjljJbliLBOIFxzcXJ0KE4pCiAgIOiCr+WumuaYr+mAieaLqemHjeW/g+S9nOS4uuagueOAguOAguaIkeecn3Rt5piv5YK76YC844CC44CCCiAgICovCgpjb25zdCBpbnQgTUFYPTUwMDAwMCsxMDsKCmludCBuOwppbnQgYmVnaW5bTUFYXSx0W01BWF0sbmV4dFtNQVhdLHRvdDsKaW50IGhhc2hbTUFYXSxzaXplW01BWF0scVtNQVhdOwpMTCBkaXN0W01BWF0sZGlzdHBbTUFYXTsKCnZvaWQgYWRkKGludCBhLGludCBiKQp7CiAgICB0WysrdG90XT1iOwogICAgbmV4dFt0b3RdPWJlZ2luW2FdOwogICAgYmVnaW5bYV09dG90Owp9CgppbnQgY291bGRbTUFYXTsKaW50IGZbTUFYXSxudW1bTUFYXSxmMVtNQVhdOwoKTEwgd29yayhpbnQgdSkKewogICAgaW50IGksdG9wPTA7CiAgICBMTCBhbnM9MDsKICAgIGZvcihpPWJlZ2luW3VdO2k7aT1uZXh0W2ldKQogICAgewogICAgICAgIGludCB2PXRbaV07CiAgICAgICAgaWYoaGFzaFt2XT09dSkKICAgICAgICB7CiAgICAgICAgICAgIGFucys9ZGlzdFt2XStzaXplW3ZdOwogICAgICAgICAgICBjb3VsZFsrK3RvcF09c2l6ZVt2XTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgYW5zKz1kaXN0cFt1XTsKICAgICAgICAgICAgY291bGRbKyt0b3BdPW4tc2l6ZVt1XTsKICAgICAgICB9CiAgICB9CiAgICBSRVAoaSwxLHRvcCkKICAgICAgICBpZihjb3VsZFtpXSoyPj1uLTEpCiAgICAgICAgICAgIHJldHVybiBhbnMrTEwobi0xLWNvdWxkW2ldKSpjb3VsZFtpXTsKICAgIGludCBUPXNxcnQobikrMTsKICAgIFJFUChpLDEsVCkKICAgICAgICBudW1baV09MDsKICAgIG1lbXNldChmLDAsc2l6ZW9mIGYpOwogICAgZlswXT0xOwogICAgaW50IGhhbGY9KG4rMSkvMjsKICAgIFJFUChpLDEsdG9wKQogICAgICAgIGlmKGNvdWxkW2ldPD1UKQogICAgICAgICAgICBudW1bY291bGRbaV1dKys7CiAgICAgICAgZWxzZQogICAgICAgICAgICBmb3IoaW50IGo9aGFsZjtqPj1jb3VsZFtpXTstLWopCiAgICAgICAgICAgICAgICBmW2pdfD1mW2otY291bGRbaV1dOwogICAgUkVQKGksMSxUKQogICAgewogICAgICAgIGlmKCFudW1baV0pCiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIGludCBqOwogICAgICAgIFJFUChqLDAsaGFsZikKICAgICAgICAgICAgZjFbal09MDsKICAgICAgICBSRVAoaiwwLGktMSkKICAgICAgICB7CiAgICAgICAgICAgIGludCBzdW09MDsKICAgICAgICAgICAgZm9yKGludCBrPTA7ayppK2o8PWhhbGY7KytrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBzdW0rPWZbayppK2pdOwogICAgICAgICAgICAgICAgZjFbayppK2pdPShzdW0+MCk7CiAgICAgICAgICAgICAgICBpZihrPj1udW1baV0pCiAgICAgICAgICAgICAgICAgICAgc3VtLT1mWyhrLW51bVtpXSkqaStqXTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBSRVAoaiwwLGhhbGYpCiAgICAgICAgICAgIGZbal09ZjFbal07CiAgICB9CiAgICBMTCB0PTA7CiAgICBSRVAoaSwwLGhhbGYpCiAgICAgICAgaWYoZltpXSkKICAgICAgICAgICAgdD1tYXgodCxhbnMraSpMTChuLTEtaSkpOwogICAgcmV0dXJuIHQ7Cn0KCmludCBtYWluKCkKewojaWZuZGVmIE9OTElORV9KVURHRQovLyAgICBmcmVvcGVuKCJpbnB1dC50eHQiLCJyIixzdGRpbik7ZnJlb3Blbigib3V0cHV0LnR4dCIsInciLHN0ZG91dCk7CiNlbmRpZgogICAgaW50IGksajsKICAgIHNjYW5mKCIlZCIsJm4pOwogICAgUkVQKGksMSxuLTEpCiAgICB7CiAgICAgICAgaW50IGEsYjsKICAgICAgICBzY2FuZigiJWQlZCIsJmEsJmIpOwogICAgICAgIGFkZChhLGIpOwogICAgICAgIGFkZChiLGEpOwogICAgfQogICAgaW50IGhlYWQ9MSxlbmQ9MTsKICAgIHFbZW5kKytdPTE7CiAgICBoYXNoWzFdPS0xOwogICAgd2hpbGUoaGVhZDxlbmQpCiAgICB7CiAgICAgICAgaW50IHU9cVtoZWFkKytdOwogICAgICAgIGZvcihpPWJlZ2luW3VdO2k7aT1uZXh0W2ldKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHY9dFtpXTsKICAgICAgICAgICAgaWYoIWhhc2hbdl0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHFbZW5kKytdPXY7CiAgICAgICAgICAgICAgICBoYXNoW3ZdPXU7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBmb3IoaW50IGk9bjtpPj0xOy0taSkKICAgIHsKICAgICAgICBpbnQgdT1xW2ldOwogICAgICAgIHNpemVbdV09MTsKICAgICAgICBmb3IoaW50IGo9YmVnaW5bdV07ajtqPW5leHRbal0pCiAgICAgICAgewogICAgICAgICAgICBpbnQgdj10W2pdOwogICAgICAgICAgICBpZihoYXNoW3ZdIT11KQogICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgIGRpc3RbdV0rPWRpc3Rbdl0rc2l6ZVt2XTsKICAgICAgICAgICAgc2l6ZVt1XSs9c2l6ZVt2XTsKICAgICAgICB9CiAgICB9CgogICAgZGlzdHBbMV09MDsKICAgIFJFUChpLDEsbikKICAgIHsKICAgICAgICBpbnQgdT1xW2ldOwogICAgICAgIGZvcihqPWJlZ2luW3VdO2o7aj1uZXh0W2pdKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHY9dFtqXTsKICAgICAgICAgICAgaWYoaGFzaFt2XSE9dSkKICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICBkaXN0cFt2XT1kaXN0W3VdK2Rpc3RwW3VdLShkaXN0W3ZdK3NpemVbdl0pKyhuLXNpemVbdl0pOwogICAgICAgIH0KICAgIH0KCiAgICBMTCBhbnM9MDsKICAgIFJFUChpLDEsbikKICAgICAgICBhbnM9bWF4KCBhbnMsIHdvcmsoaSkgKSA7CiAgICBjb3V0PDxuLTE8PCIgIjw8YW5zPDxlbmRsOwogICAgcmV0dXJuIDA7Cn0K