Submission #1217238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217238		Ak_16	Chorus (JOI23_chorus)	C++20	In queue	0 ms	0 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[2005];
int st[2005];
int par[2005];
int dep[2005];
int lis[100];
int nolis[105];
int mx;
int n;

int con[2005];
int psum[105];
int ssum[105];


int dp[100][100];

void dfs(int no, int pa){
     for(auto x : adj[no]){
        if(x!=pa){
            dfs(x, no);
            st[no] += st[x];
            con[no] -= (st[x]) * (st[x]-1) / 2;
        }
     }
     con[no] -= (n-st[no])*(n-st[no]-1) / 2;
     con[no]++;
     return;
}

void dfs2(int no, int pa){

   dep[no] = dep[pa] + 1;
   par[no] = pa;

    for(auto x : adj[no]){
        if(x!=pa){
            dfs2(x, no);
        }
    }
    return;
}
void dfs3(int no, int pa){
    for(auto x : adj[no]){
        if(x!=pa){
            dfs3(x, no);
            st[no] += st[x];
        }
    }
    return;
}

   
   

   
   


int main(){
    cin.tie(nullptr);
    int t,u,v;
    int deg[10005];
    for(int i=0; i<=99; i++){
        for(int j=0; j<=99; j++){
            dp[i][j] = 0;
        }
    }

    int mxd=0;

    dep[0] = -1;

    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1; i<=n; i++){
            adj[i].clear();
            deg[i] = 0;
            st[i] = 1;
        }
        for(int i=1; i<=n; i++){
            con[i] = n*(n-1)/2;
        }

        for(int i=1; i<n; i++){
            cin>>u>>v;
            adj[u].push_back(v);
            adj[v].push_back(u);
            deg[u]++;
            deg[v]++;
        }

        mxd = 0;

        for(int i=1; i<=n; i++){
            mxd = max(mxd, deg[i]);
        }

        if(mxd==2){cout<<2*n-1<<" ";}
        else {cout<<n+1<<" ";}
        
        mx = 0;

        dfs(1, 0);
        

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
               
                if(j==i){continue;}

                dep[0] = -1;
                dfs2(i, 0);

                for(int k=1; k<=n; k++){
                    st[k] = 1;
                }

                dfs3(i, 0);
                int num = dep[j];
                

                for(int l=1; l<=dep[j]+1; l++){
                    for(int r=l; r<=dep[j]+1; r++){
                        dp[l][r] = 0;
                    }
                }

                for(int k = j; k!=0; k=par[k]){
                    lis[dep[k]+1] = k;
                }

                for(int k=1; k<=num+1; k++){
                    if(k==1){nolis[k] = 1;}
                    else if(k==num+1){nolis[k] = 1;}
                    else {
                        nolis[k] = st[lis[k]] - st[lis[k+1]];
                    }
                }

                psum[0] = 0;
                ssum[num+2] = 0;

                for(int k=1; k<=num+1; k++){
                    psum[k] = psum[k-1] + nolis[k];
                }

                for(int k=num+1; k>=1; k--){
                    ssum[k] = ssum[k+1] + nolis[k];
                }



                for(int pl = 0; pl<=dep[j]; pl++){
                   for(int l=1; l<=num+1-pl; l++){
                    if(pl==0){dp[l][l] = con[lis[l]];}

                    else {
                       dp[l][l+pl] = psum[l] * ssum[l+pl] + max(dp[l][l+pl-1], dp[l+1][l+pl]);
                    }
                   }
                }

               mx = max(mx, dp[1][num+1]);

               
            }
        }

        
        cout<<mx<<endl;
        

    }
}