Submission #60986670

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
namespace SOLUTION{
  const int maxn=3e5+5;
  vector<int>e[maxn];
  int fa[maxn],siz[maxn];
  inline void prework(int u,int father){
    fa[u]=father;
    siz[u]=1;
    for(int v:e[u]){
      if(v!=father){
        prework(v,u);
        ++siz[u];
      }
    }
  }
  int ans=0;
  int vec[maxn];
  inline void dfs(int u){
    int cnt=0;
    for(int v:e[u]){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;
namespace SOLUTION{
	const int maxn=3e5+5;
	vector<int>e[maxn];
	int fa[maxn],siz[maxn];
	inline void prework(int u,int father){
		fa[u]=father;
		siz[u]=1;
		for(int v:e[u]){
			if(v!=father){
				prework(v,u);
				++siz[u];
			}
		}
	}
	int ans=0;
	int vec[maxn];
	inline void dfs(int u){
		int cnt=0;
		for(int v:e[u]){
			vec[++cnt]=siz[v];
		}
		sort(vec+1,vec+cnt+1);
		for(int i=1;i<=cnt;++i){
			if(vec[i]>=2){
				ans=max(ans,1+(cnt-i+1)*vec[i]);
			}
		}
		for(int v:e[u]){
			if(v!=fa[u]){
				--siz[u],++siz[v];
				dfs(v);
				++siz[u],--siz[v];
			}
		}
	}
	inline int Main(){
		int n;
		cin>>n;
		for(int i=1;i<n;++i){
			int u,v;
			cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		prework(1,0);
		dfs(1);
		cout<<n-ans<<"\n";
		return 0;
	}
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	SOLUTION::Main();
	return 0;
}

Submission Info

Judge Result