Submission #1692361

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
#define inf 2147483647
#define ll long long
#define pa(a, b) (data){a, b}
using namespace std;

struct edge{int x, y, next;}a[N*2];
struct data{int def, sum;}d[N];
int n, l, p[N], x, y, def[N], def1[N], sum[N], def_fa[N], fa[N], mx, mx1, R, L;
ll ans;
char S[N];

inline void add(int x, int y){a[++l].x=x; a[l].y=y; a[l].next=p[x]; p[x]=l;}
inline void dfs(int x){
	def[x]=def1[x]=1; sum[x]=S[x]=='1'?1:0;
	for(int i=p[x]; i; i=a[i].next)if(fa[x]!=a[i].y){
		fa[a[i].y]=x; dfs(a[i].y); sum[x]+=sum[a[i].y];
		if(def[x]<=def[a[i].y]+1){def1[x]=def[x]; def[x]=def[a[i].y]+1;}
		else if(def1[x]<=def[a[i].y]+1)def1[x]=def[a[i].y]+1;
	}
}
inline void dp(int x){
	for(int i=p[x]; i; i=a[i].next)if(fa[x]!=a[i].y){
		if(def[x]==def[a[i].y]+1)def_fa[a[i].y]=max(def_fa[x], def1[x])+1;
		else def_fa[a[i].y]=max(def_fa[x], def[x])+1;
		dp(a[i].y);
	}
}

int main(){
	scanf("%d", &n);
	l=0; memset(p, 0, sizeof(p));
	for(int i=1; i<=n-1; i++){scanf("%d%d", &x, &y); add(x, y); add(y, x);}
	scanf("%s", S+1);
	fa[1]=1; dfs(1);
	def_fa[1]=0; dp(1);
	ans=1; //全集
	for(int i=1; i<=n; i++){
		l=0;
		for(int j=p[i]; j; j=a[j].next)
			if(fa[i]==a[j].y)d[++l]=pa(def_fa[i]-1, sum[1]-sum[i]);
			else d[++l]=pa(def[a[j].y], sum[a[j].y]);
		mx=mx1=0;
		for(int j=1; j<=l; j++)
			if(mx<=d[j].def){mx1=mx; mx=d[j].def;}
			else if(mx1<=d[j].def)mx1=d[j].def;
		R=min(mx1+1, mx-1);
		if(R==-1)continue;
		if(S[i]=='1'){ans+=R+1; continue;}
		L=inf;
		for(int j=1; j<=l; j++)if(d[j].sum)L=min(L, d[j].def);
		if(L<=R)ans+=R-L+1;
	}
	printf("%lld", ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:34:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:36:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n-1; i++){scanf("%d%d", &x, &y); add(x, y); add(y, x);}
                                                 ^
./Main.cpp:37:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", S+1);
                  ^

Judge Result