fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. /*
  27.    考虑如何计算出互相可达的点对数量吧
  28.    情况实在太过复杂了啊
  29. qewss`
  30.    //题解nmb
  31.    //问题是我60分都不会啊
  32.  
  33.    点对除了使用lca计算以外还有什么办法？
  34.  
  35.    与每个点连通的点的数量。。
  36.    f1[i][j] 表示以点i为根，在i的祖先中点i能够到达的点的数量为j的最优值
  37.    f2[i][j] 表示以点i为根，在i的子孙中能够到达的点的数量为j的最优值
  38.  
  39.    f1[i][j] 的计算貌似可以dp啊
  40.    若枚举点i能够到达的连通块。。
  41.  
  42.    这个算法是n^3的，稍微靠谱点，但还是不是n^2的
  43.  
  44.    思路依旧是对于点i，得知其能到达的点的个数。。
  45.    由于在原来的转移中对于f1的转移为O(1)。。。
  46.  
  47.    难道还是要使用LCA么。。
  48.    我觉得肯定不行啊。。
  49.  
  50.    所以说还是结论题：
  51.    一定是有一个中心，mb如果知道这个了的话这题还有毛意思啊。。
  52.  
  53.    sum=a+b+c+d
  54.    ab+bc+cd<max( (a+b)*(c+d), (sum-a)*a,(sum-b)*b,(sum-c)*c,(sum-d)*d)
  55.    擦。。。
  56.  
  57.    枚举中心点可秒啊。。
  58.    可以得到各种各样的东东。。
  59.  
  60.    但是这样还是不会优化到N \sqrt(N)
  61.    肯定是选择重心作为根。。我真tm是傻逼。。
  62.    */
  63.  
  64. const int MAX=500000+10;
  65.  
  66. int n;
  67. int begin[MAX],t[MAX],next[MAX],tot;
  68. int hash[MAX],size[MAX],q[MAX];
  69. LL dist[MAX],distp[MAX];
  70.  
  71. void add(int a,int b)
  72. {
  73.     t[++tot]=b;
  74.     next[tot]=begin[a];
  75.     begin[a]=tot;
  76. }
  77.  
  78. int could[MAX];
  79. int f[MAX],num[MAX],f1[MAX];
  80.  
  81. LL work(int u)
  82. {
  83.     int i,top=0;
  84.     LL ans=0;
  85.     for(i=begin[u];i;i=next[i])
  86.     {
  87.         int v=t[i];
  88.         if(hash[v]==u)
  89.         {
  90.             ans+=dist[v]+size[v];
  91.             could[++top]=size[v];
  92.         }
  93.         else
  94.         {
  95.             ans+=distp[u];
  96.             could[++top]=n-size[u];
  97.         }
  98.     }
  99.     REP(i,1,top)
  100.         if(could[i]*2>=n-1)
  101.             return ans+LL(n-1-could[i])*could[i];
  102.     int T=sqrt(n)+1;
  103.     REP(i,1,T)
  104.         num[i]=0;
  105.     memset(f,0,sizeof f);
  106.     f[0]=1;
  107.     int half=(n+1)/2;
  108.     REP(i,1,top)
  109.         if(could[i]<=T)
  110.             num[could[i]]++;
  111.         else
  112.             for(int j=half;j>=could[i];--j)
  113.                 f[j]|=f[j-could[i]];
  114.     REP(i,1,T)
  115.     {
  116.         if(!num[i])
  117.             continue;
  118.         int j;
  119.         REP(j,0,half)
  120.             f1[j]=0;
  121.         REP(j,0,i-1)
  122.         {
  123.             int sum=0;
  124.             for(int k=0;k*i+j<=half;++k)
  125.             {
  126.                 sum+=f[k*i+j];
  127.                 f1[k*i+j]=(sum>0);
  128.                 if(k>=num[i])
  129.                     sum-=f[(k-num[i])*i+j];
  130.             }
  131.         }
  132.         REP(j,0,half)
  133.             f[j]=f1[j];
  134.     }
  135.     LL t=0;
  136.     REP(i,0,half)
  137.         if(f[i])
  138.             t=max(t,ans+i*LL(n-1-i));
  139.     return t;
  140. }
  141.  
  142. int main()
  143. {
  144. #ifndef ONLINE_JUDGE
  145. //    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  146. #endif
  147.     int i,j;
  148.     scanf("%d",&n);
  149.     REP(i,1,n-1)
  150.     {
  151.         int a,b;
  152.         scanf("%d%d",&a,&b);
  153.         add(a,b);
  154.         add(b,a);
  155.     }
  156.     int head=1,end=1;
  157.     q[end++]=1;
  158.     hash[1]=-1;
  159.     while(head<end)
  160.     {
  161.         int u=q[head++];
  162.         for(i=begin[u];i;i=next[i])
  163.         {
  164.             int v=t[i];
  165.             if(!hash[v])
  166.             {
  167.                 q[end++]=v;
  168.                 hash[v]=u;
  169.             }
  170.         }
  171.     }
  172.     for(int i=n;i>=1;--i)
  173.     {
  174.         int u=q[i];
  175.         size[u]=1;
  176.         for(int j=begin[u];j;j=next[j])
  177.         {
  178.             int v=t[j];
  179.             if(hash[v]!=u)
  180.                 continue;
  181.             dist[u]+=dist[v]+size[v];
  182.             size[u]+=size[v];
  183.         }
  184.     }
  185.  
  186.     distp[1]=0;
  187.     REP(i,1,n)
  188.     {
  189.         int u=q[i];
  190.         for(j=begin[u];j;j=next[j])
  191.         {
  192.             int v=t[j];
  193.             if(hash[v]!=u)
  194.                 continue;
  195.             distp[v]=dist[u]+distp[u]-(dist[v]+size[v])+(n-size[v]);
  196.         }
  197.     }
  198.  
  199.     LL ans=0;
  200.     REP(i,1,n)
  201.         ans=max( ans, work(i) ) ;
  202.     cout<<n-1<<" "<<ans<<endl;
  203.     return 0;
  204. }
  205.  
Success #stdin #stdout 0s 30648KB
comments (?)
stdin
copy 
7
1 2
1 3
1 4
5 1
6 1
7 1
stdout
copy 
6 15
https://ideone.com/WOjiy3
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!