Submission #60975794

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>
#define int long long
#define f(i,j,n) for(int i=j;i<=n;i++)
#define F(i,n,j) for(int i=n;i>=j;i--)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
#define pb push_back
#define XQZ
using namespace std;
namespace fsd{
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
  const int MAXSIZE=1<<20;
  char buf[MAXSIZE],*p1,*p2;
  inline int read(){
    int ak=0,ioi=1;char c=gc();
    while(!isdigit(c)){if(c=='-')ioi=-1;c=gc();}
    while(isdigit(c))ak=ak*10+(c^48),c=gc();
    return ak*ioi;
  }
  inline string reads(){
    string o="";
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define int long long
#define f(i,j,n) for(int i=j;i<=n;i++)
#define F(i,n,j) for(int i=n;i>=j;i--)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
#define pb push_back
#define XQZ
using namespace std;
namespace fsd{
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
	const int MAXSIZE=1<<20;
	char buf[MAXSIZE],*p1,*p2;
	inline int read(){
		int ak=0,ioi=1;char c=gc();
		while(!isdigit(c)){if(c=='-')ioi=-1;c=gc();}
		while(isdigit(c))ak=ak*10+(c^48),c=gc();
		return ak*ioi;
	}
	inline string reads(){
		string o="";
		char p=gc();
		while(p>'z'||p<'a'){p=gc();}
		while(p<='z'&&p>='a'){o+=p;p=gc();}
		return o;
	}
	inline char readc(){
		char p=gc();
		while(!((p<='z'&&p>='a')||(p<='Z'&&p>='A'))){p=gc();}
		return p;
	}
	inline long double readd(){
		long double ak=0;int ioi=1;char c=gc();
		while(!isdigit(c)){if(c=='-')ioi=-1;c=gc();}
		while(isdigit(c))ak*=10,ak+=c-'0',c=gc();
		c=gc();
		long double q=0.1;
		while(isdigit(c))ak+=(c-'0')*q,q*=0.1,c=gc();
		return ak*ioi;
	}
}
using namespace fsd;
const int N=3e5+10;
int n;
vector<int> h[N];
int downs[N];
int up2[N];
void dfs(int k,int prt){
	downs[k]=h[k].size()-!!prt;
	for(auto v:h[k]){
		if(v==prt)continue;
		dfs(v,k);
	}
}
int ans=0;
vector<int> uu;
void dfs1(int k,int prt,int upc){
	int sm=upc,minn=(prt?upc:LLONG_MAX/2);
	for(auto v:h[k]){
		if(v==prt)continue;
		dfs1(v,k,downs[k]+(!!prt));
		sm+=downs[v]+1;
		updmin(minn,downs[v]+1);
	}
	uu.clear();
	if(prt)uu.push_back(upc);
	for(auto v:h[k]){
		if(v==prt)continue;
		uu.push_back(downs[v]+1);
	}
	sort(uu.begin(),uu.end());
	int lv=downs[k]+!!prt;
	for(auto v:uu){
		updmax(ans,1+v*lv);
		lv--;
	}
}
void gs(){
	cin>>n;
	f(i,1,n-1){
		int p,q;cin>>p>>q;
		h[p].push_back(q);
		h[q].push_back(p);
	}
	dfs(1,0);
	dfs1(1,0,0);
	cout<<n-ans<<endl;
}
signed main(){
#ifndef XQZ
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
#ifdef NXD
	int t=0;cin>>t;while(t--)
#endif
		gs();
	return 0;
}

Submission Info

Judge Result