Submission #60974630

---

Source Code Expand

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

const int MAX=3e5+11;

int n;
vector<int> adj[MAX];
int sz[MAX];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;

        adj[u].push_back(v);
        adj[v].push_back(u);
        sz[u]++;
        sz[v]++;
    }

    int ans=0;
    for(int u=1;u<=n;u++)
    {
        vector<int> v;
        int cnt=sz[u];
        for(int x: adj[u]) v.push_back(sz[x]-1);

        sort(v.begin(),v.end());
        for(int i=0;i<cnt;i++)
        {
            int x=cnt-i;
            int y=v[i];
            ans=max(ans,1+x+x*y);
        }
    }

    cout<<n-ans<<"\n";

    return 0;
}

Submission Info

Judge Result