Submission #1205651

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

int N;
const int MN=400000;
string s;

using Data = pair<int,int>;
using SubData = pair<int,int>; //depth,has1

vector<int> G[MN];
int par[MN];
Data dp[MN];			//0-rooted dp[v]=term(merge(dp[u1],dp[u2],...))
SubData dp_nottermed[MN];	//0-rooted merge(dp[u1],...)
Data up[MN];			//up[v]= 0-rootedでのvの親をpとして, v->p方向のdpの値 term(merge(up[p],dp[v's bro1],dp[v's bro1],...))
Data DP[MN];			//DP[v]: ans for v-rooted tree
vector<SubData> ls,rs;		//ls/rs[i] = 0-rootedで見てvのchildrenを左/右からi個mergeしたもの(各vで使い回す)
SubData init(0,0);

SubData merge(SubData val,Data v){
	return SubData(max(val.fs,v.fs+1),max(val.sc,v.sc));
}
SubData merge2(SubData x,SubData y){
	return SubData(max(x.fs,y.fs),max(x.sc,y.sc));
}
Data term(SubData val,int v){
	return Data(val.fs,val.sc|(s[v]=='1'));
}
void dfs(int v,int p=-1){
	par[v]=p;
	SubData val=init;
	for(int u:G[v]) if(u!=p){
		dfs(u,v);
		val=merge(val,dp[u]);
	}
	dp_nottermed[v]=val;
	dp[v]=term(val,v);
//	cout<<"dp["<<v<<"]="<<dp[v]<<endl;
}
void ufs(int v,int p=-1){		//0-rootedでupwardな部分を計算
	vector<int> ch;	//children
	for(int u:G[v]) if(u!=p) ch.pb(u);
	int K=ch.size();
	ls.resize(K+1);
	rs.resize(K+1);
	ls[0]=init;
	rs[0]=init;
	rep(i,K){
		ls[i+1]=merge(ls[i],dp[ch[i]]);
		rs[i+1]=merge(rs[i],dp[ch[K-1-i]]);
	}
//	if(p==-1) rep1(i,K) show(ls[i]),show(rs[i]);
	rep(i,K){
		int u=ch[i];
		SubData val=merge2(ls[i],rs[K-1-i]);
		if(p>=0) val=merge(val,up[v]);
		up[u]=term(val,v);
//		cout<<"up["<<u<<"]="<<up[u]<<endl;
	}
	rep(i,K) ufs(ch[i],v);
}
void calcDP(int N,int r=0){
	dfs(r);
//	up[r]=e			//Dataの単位元(≠init)が必要で面倒なので回避
	ufs(r);
	rep(v,N){
		SubData val=dp_nottermed[v];
		if(v!=r) val=merge(val,up[v]);
		DP[v]=term(val,v);
	}
}
int inf = 1e9;
int main(){
	int N;
	cin>>N;
	rep(i,N-1){
		int e = N+i;
		int x,y;
		scanf("%d %d",&x,&y);
		x--,y--;
		G[x].pb(e);G[e].pb(x);
		G[y].pb(e);G[e].pb(y);
	}
	cin>>s;
	s+=string(N-1,'0');
	calcDP(2*N-1);
	long long ans=0;

	rep(r,2*N-1){
		int mx=-inf,mx2=-inf;
		int hasmin=inf;
		for(int u:G[r]){
			Data p = (u==par[r]?up[r]:dp[u]);
			int d = p.fs+1;
			int has = p.sc;
//			printf("%d->%d  d=%d\n",r,u,d);
			if(has) chmin(hasmin,d);
			if(mx<d){
				mx2=mx;
				mx=d;
			}else if(mx2<d){
				mx2=d;
			}
		}
		int tmp=0;
		if(r<N){	//vertex
			if(mx2==-inf) mx2=0;
//			show(hasmin);
			assert(mx2%2==0);
			assert(hasmin%2==0);
			int x = mx2/2;
//			show(x);
			int y = hasmin/2;
			if(s[r]=='1') y=0;
			tmp=max(0,x-y+1);
		}else{
			assert(mx2!=-inf);
			assert(mx2%2==1);
			assert(hasmin%2==1);
			int x = mx2/2;
			int y = hasmin/2;
			tmp=max(0,x-y+1);
		}
//		printf("v=%d;  +=%d\n",r,tmp);
		ans+=tmp;
	}
	cout<<ans<<endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:90:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
                       ^

Judge Result