Submission #69744956

---

Source Code Expand

// 华风夏韵 洛水天依
// 天依宝宝可爱！> <

#include<bits/stdc++.h>

#define int long long
#define double long double
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rpe(i,a,b) for(int i=(a);i>=(b);--i)
#define repp(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define rpee(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define inf (int)(0x3f3f3f3f3f3f3f3f)
#define pii pair <int,int>
#define st first
#define nd second
#define mp make_pair
#define pb emplace_back
#define all(x) (x).begin(),(x).end()
#define mxele *max_element
#define mnele *min_element
#define gsum(l,r) accumulate((l),(r),0ll)
#define umap unordered_map
#define uset unordered_set
#define prque(a,b) priority_queue <a,vector<a>,b<a>>
#define popc __builtin_popcount
#define lowb lower_bound
#define uppb upper_bound

using namespace std;
bool memory_begin;

#ifdef ONLINE_JUDGE
#define is_debug 0
#else
#define is_debug 1
#endif

#define multiple_test 0
#define mod 998244353

namespace fast_io{char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny,precision=19;bool isEOF=0;unsigned long long pw10[20];il bool init_pw10(){pw10[0]=1ull;rep(i,1,19)pw10[i]=pw10[i-1]*10ull;return 1;}il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}il int read(){int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc^EOF)nc==45&&(ny=-1);Bi=1;if(nc<0)return isEOF=1,nc;x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc^EOF)x=(x<<3)+(x<<1)+(nc^48),++Bi;return x*ny;}il void read(int &x){x=read();}il void read(char &x){while(nc=gc(),nc<33&&nc^EOF);nc<0&&(isEOF=1);x=nc;}il void read(pii&a){a.st=read(),a.nd=read();}il void read(double &x){pw10[0]||init_pw10();int a=read(),y=ny,b=(nc!='.')?0:read();x=(b?a+(double)b/pw10[Bi]*y:a);}il void read(string &s){s="";while(nc=gc(),nc<33&&nc^EOF);nc<0&&(isEOF=1);s+=nc;while(nc=gc(),nc>=33)s+=nc;}il signed read(char *s){char *t=s;while(nc=gc(),nc<33&&nc^EOF);nc<0&&(isEOF=1);*s++=nc;while(nc=gc(),nc>=33)*s++=nc;return s-t;}template <typename T,typename ... Args> il void read(T &x, Args &... y) {read(x);read(y...);}il void ot(){fwrite(sr,1,C+1,stdout);C=-1;}il void flush(){if(C>1<<22)ot();}il void pc(char c){sr[++C]=c;flush();}il void write(int x,char t='\0'){int y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);t=='\0'||(sr[++C]=t);flush();}il void write(char x,char t='\0'){sr[++C]=x,t=='\0'||(sr[++C]=t);flush();}il void write(pii a,char t='\0'){write(a.st,' '),write(a.nd,t);flush();}il void write(double x,char t='\0'){pw10[0]||init_pw10();write((int)x,'.'),write((int)((x-(int)x)*pw10[precision]),t);flush();}il void write(string s,char t='\0'){int l=s.size();rep(i,0,l-1)sr[++C]=s[i];t=='\0'||(sr[++C]=t);flush();}il void write(char *s,char t='\0'){int l=strlen(s);rep(i,0,l-1)sr[++C]=*s++;t=='\0'||(sr[++C]=t);flush();}template <typename T,typename ... Args> il void write(T x, Args ... y){write(x,' ');write(y...);}}
using fast_io::read,fast_io::write;
namespace _{template <typename T> il void r(T*a,int n){rep(i,1,n)read(a[i]);}template <typename T1,typename T2> il void r(T1 *a,T2 *b,int n){rep(i,1,n)read(a[i]),read(b[i]);}template <typename T1,typename T2,typename T3> il void r(T1 *a,T2 *b,T3 *c,int n){rep(i,1,n)read(a[i]),read(b[i]),read(c[i]);}template <typename T> il void r(T*a,int n,int m){rep(i,1,n)rep(j,1,m)read(a[i][j]);}template <typename T> il void r(vector<T>&a,int n){a.resize(n);rep(i,0,n-1)read(a[i]);}template <typename T> il void r(vector<T>*p,int m,bool op){int u,v;rep(i,1,m)read(u,v),p[u].pb(v),op||(p[v].pb(u),1);}template <typename T1,typename T2> il void r(vector<pair<T1,T2>>*p,int m,bool op){int u,v,w;rep(i,1,m)read(u,v,w),p[u].pb(v,w),op||(p[v].pb(u,w),1);}template <typename T> il void w(T*a,int n){rep(i,1,n-1)write(a[i],' ');n&&(write(a[n]),1),write('\n');}template <typename T> il void w(T*a,int n,int m){rep(i,1,n){rep(j,1,m-1)write(a[i][j],' ');m&&(write(a[i][m]),1),write('\n');}}template <typename T> il void w(vector<T>&a){rep(i,0,(int)a.size()-2)write(a[i],' ');!a.empty()&&(write(a.back()),1),write('\n');}}
namespace dbg{template <typename T> il void arr(T*a,int n){if(!is_debug)return;rep(i,1,n-1)cerr<<a[i]<<' ';n&&(cerr<<a[n],1),cerr<<'\n';} template <typename T> il void arr(string s,T *a,int n){if(!is_debug)return;cerr<<s<<" : ";arr(a,n);}template <typename T> il void mat(T*a,int n,int m){if(!is_debug)return;rep(i,1,n){rep(j,1,m-1)cerr<<a[i][j]<<' ';m&&(cerr<<a[i][m],1),cerr<<'\n';}cerr<<'\n';} template <typename T> il void mat(string s,T *a,int n,int m){if(!is_debug)return;cerr<<s<<" :\n";mat(a,n,m);}template <typename T> il void vec(vector<T>a){if(!is_debug)return;rep(i,0,(int)a.size()-2)cerr<<a[i]<<' ';!a.empty()&&(cerr<<a.back(),1),cerr<<'\n';} template <typename T> il void vec(string s,vector <T> a){if(!is_debug)return;cerr<<s<<" : ";vec(a);}template <typename T> il void graV(vector<T>*p,int n){if(!is_debug)return;rep(u,1,n){cerr<<u<<" : ";rep(i,0,(int)p[u].size()-2)cerr<<p[u][i]<<' ';!p[u].empty()&&(cerr<<p[u].back(),1),cerr<<'\n';}cerr<<'\n';} template <typename T> il void graV(string s,vector <T> *p,int n){if(!is_debug)return;cerr<<s<<" :\n";graV(p,n);}template <typename T1,typename T2> il void graV(vector<pair<T1,T2>>*p,int n){if(!is_debug)return;rep(u,1,n){cerr<<u<<" : ";rep(i,0,(int)p[u].size()-2)cerr<<p[u][i].st<<','<<p[u][i].nd<<' ';!p[u].empty()&&(cerr<<p[u].back().st<<','<<p[u].back().nd,1),cerr<<'\n';}cerr<<'\n';} template <typename T1,typename T2> il void graV(string s,vector <pair<T1,T2>> *p,int n){if(!is_debug)return;cerr<<s<<" :\n";graV(p,n);}template <typename T> il void graE(vector<T>*p,int n,bool op){if(!is_debug)return;rep(u,1,n)for(auto v:p[u])(op||u<v)&&(cerr<<u<<' '<<v<<'\n',1);cerr<<'\n';} template <typename T> il void graE(string s,vector <T> *p,int n,bool op){if(!is_debug)return;cerr<<s<<" :\n";graE(p,n,op);}template <typename T1,typename T2> il void graE(vector<pair<T1,T2>>*p,int n,bool op){if(!is_debug)return;rep(u,1,n)for(auto [v,w]:p[u])(op||u<v)&&(cerr<<u<<' '<<v<<' '<<w<<'\n',1);cerr<<'\n';} template <typename T1,typename T2> il void graE(string s,vector <pair<T1,T2>> *p,int n,bool op){if(!is_debug)return;cerr<<s<<" :\n";graE(p,n,op);}}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
il double gtime(){return clock()*1e3/CLOCKS_PER_SEC;}
template <typename T> il void clr(T &x){T().swap(x);}
template <typename T1,typename T2> il T1& add(T1 &a,T2 b){(a+=b)>=0?(a>=mod&&(a-=mod)):(a+=mod);return a;}
template <typename T1,typename T2> il T1& chmax(T1 &a,T2 b){return a<b&&(a=b,1),a;}
template <typename T1,typename T2> il T1& chmin(T1 &a,T2 b){return a>b&&(a=b,1),a;}

#if mod==998244353
il long long mod_(const long long &x){unsigned long long ux=(x>=0?x:-x),r=ux-(__uint128_t(ux)*9920937979283557439ull>>93)*998244353; return x>=0?r:mod-r;}
#elif mod==1000000007
il long long mod_(const long long &x){unsigned long long ux=(x>=0?x:-x),r=ux-(__uint128_t(ux)*9903520244958400484ull>>93)*1000000007; return x>=0?r:mod-r;}
#else
il long long mod_(const long long &x){return x<0?x%mod+mod:x%mod;}
#endif

#if !is_debug
#define fprintf(...) (1)
struct __null_stream{template<typename T>__null_stream& operator<<(const T&){return *this;}};
static __null_stream null_stream;
#define cerr null_stream
#endif

const int N=2e5+5,M=6e5+5,V=6e5+5;
const int dx[10]={0,0,1,0,-1,1,1,-1,-1},dy[10]={0,1,0,-1,0,1,-1,1,-1};
const double eps=1e-9;

int __T=1,test_case;

struct state
{
	int x1,p1,x2,p2;
	state():x1(0),p1(-1),x2(0),p2(-1){}
	il void ins(int x3,int p3){x3>=x1?(x2=x1,p2=p1,x1=x3,p1=p3):(x3>=x2&&(x2=x3,p2=p3));}
	il void err(){fprintf(stderr,"(%lld,%lld) (%lld,%lld)",x1,p1,x2,p2);}
};

// === / 走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊 / ===

int n,siz[N],w[N],f[N][2],W[N],F[N][2];
state d[N],mx[N],D[N],MX[N];
vector <int> p[N];

il void dfs1(int u,int ufa)
{
	for(auto v:p[u]) v^ufa && (dfs1(v,u),1);
	
	// siz & d & w
	siz[u]=1;
	for(auto v:p[u]) v^ufa && (siz[u]+=siz[v],d[u].ins(d[v].x1+1,v),1);
// 	d[u].x1==-inf && (d[u].ins(0,u),1);
	w[u]=(siz[u]-1<<1)-d[u].x1;
	
	// f & mx
	for(auto v:p[u]) v^ufa && (f[u][1]+=min(f[v][1]+2,w[v]+1));
	for(auto v:p[u]) v^ufa && (mx[u].ins(min(f[v][1]+2,w[v]+1)-(f[v][0]+1),v),1);
//	mx[u].x1==-inf && (mx[u].ins(0,u),1);
	f[u][0]=f[u][1]-mx[u].x1;
}

il void dfs2(int u,int ufa)
{
	int t1,t2,t3;
	for(auto v:p[u]) if(v^ufa)
	{
		// D & W
		D[v]=d[v],D[v].ins((D[u].p1^v ? D[u].x1 : D[u].x2)+1,u);
		W[v]=(n-1<<1)-D[v].x1;
		
		// F & MX
		t1=F[u][1],t2=F[u][0],t3=W[u];
		
		F[u][1]-=min(f[v][1]+2,w[v]+1);
		F[u][0]=F[u][1]-(MX[u].p1^v ? MX[u].x1 : MX[u].x2);
		W[u]=(n-siz[v]-1<<1)-(D[u].p1^v ? D[u].x1 : D[u].x2);
		
		F[v][1]=f[v][1],F[v][1]+=min(F[u][1]+2,W[u]+1);
		MX[v]=mx[v],MX[v].ins(min(F[u][1]+2,W[u]+1)-(F[u][0]+1),u);
		F[v][0]=F[v][1]-MX[v].x1;
		
		F[u][1]=t1,F[u][0]=t2,W[u]=t3;
		
		// qwq
		dfs2(v,u);
	}
}

il void solve(int __Ti)
{
//    double time_begin=gtime();
	
	read(n),_::r(p,n-1,false);
	
	int rt=1;
	dfs1(rt,0);
	F[rt][0]=f[rt][0],F[rt][1]=f[rt][1],D[rt]=d[rt],MX[rt]=mx[rt],W[rt]=w[rt];
	dfs2(rt,0);
	cerr<<"rt = "<<rt<<"\n\n";
	
	rep(i,1,n-20120712)
	{
		cerr<<"u = "<<i<<" -----------------\n";
		cerr<<"   D : ",D[i].err(),cerr<<'\n';
		cerr<<"   W : "<<W[i]<<'\n';
		cerr<<"  MX : ",MX[i].err(),cerr<<'\n';
		cerr<<"  F0 : "<<F[i][0]<<'\n';
		cerr<<"  F1 : "<<F[i][1]<<'\n';
	}
	
	int ans=inf; rep(i,1,n) chmin(ans,F[i][0]);
	write(ans);
	
//    cerr<<"task "<<__Ti<<" : time = "<<gtime()-time_begin<<" ms\n";
}

il void init()
{
//    read(test_case);
	
	
}

bool memory_end;
signed main()
{
//    freopen(".in","r",stdin),freopen(".out","w",stdout);
//    ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
	fprintf(stderr,"memory = %.3lf MB\n\n",abs(&memory_end-&memory_begin)/1048576.);
	init(); multiple_test&&(read(__T),1);
	rep(__Ti,1,__T) solve(__Ti);
//    int __Ti=0; while(read(n),!fast_io::isEOF) solve(++__Ti);
	fprintf(stderr,"\ntime = %.3Lf ms\n",gtime());
	return fast_io::ot(),0;
}

Submission Info

Compile Error

Main.cpp: In member function ‘void state::ins(long long int, long long int)’:
Main.cpp:79:87: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   79 |         il void ins(int x3,int p3){x3>=x1?(x2=x1,p2=p1,x1=x3,p1=p3):(x3>=x2&&(x2=x3,p2=p3));}
      |                                                                                     ~~^~~
Main.cpp: In member function ‘void state::err()’:
Main.cpp:63:23: warning: statement has no effect [-Wunused-value]
   63 | #define fprintf(...) (1)
      |                      ~^~
Main.cpp:80:23: note: in expansion of macro ‘fprintf’
   80 |         il void err(){fprintf(stderr,"(%lld,%lld) (%lld,%lld)",x1,p1,x2,p2);}
      |                       ^~~~~~~
Main.cpp: In function ‘void dfs1(long long int, long long int)’:
Main.cpp:97:21: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
   97 |         w[u]=(siz[u]-1<<1)-d[u].x1;
      |               ~~~~~~^~
Main.cpp: In function ‘void dfs2(long long int, long long int)’:
Main.cpp:113:24: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
  113 |                 W[v]=(n-1<<1)-D[v].x1;
      |                       ~^~
Main.cpp:120:31: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
  120 |                 W[u]=(n-siz[v]-1<<1)-(D[u].p1^v ? D[u].x1 : D[u].x2);
      |                       ~~~~~~~~^~
Main.cpp: In function ‘void solve(long long int)’:
Main.cpp:133:19: warning: unused parameter ‘__Ti’ [-Wunused-parameter]
  133 | il void solve(int __Ti)
      |                   ^
Main.cpp: In function ‘int main()’:
Main.cpp:63:23: warning: statement has no effect [-Wunused-value]
   63 | #define fprintf(...) (1)
      |                      ~^~
Main.cpp:173:9: note: in expansion of macro ‘fprintf’
  173 |         fprintf(stderr,"memory = %.3lf MB\n\n",abs(&memory_end-&memory_begin)/1048576.);
      |         ^~~~~~~
Main.cpp:63:23: warning: statement has no effect [-Wunused-value]
   63 | #define fprintf(...) (1)
      |                      ~^~
Main.cpp:177:9: note: in expansion of macro ‘fprintf’
  177 |         fprintf(stderr,"\ntime = %.3Lf ms\n",gtime());
      |         ^~~~~~~

Judge Result