Submission #1045968

---

Source Code Expand

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define PR pair
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define REP(i, x, y)   for(int i = (int)(x); i <= (int)(y); i++)
#define FOR(i, x, y)   for(int i = (int)(x); i <  (int)(y); i++)
#define PER(i ,x, y)  for(int i = (int)(x); i >= (int)(y); i--)
#define CH	         ch = getchar()
#define Exit(...)    printf(__VA_ARGS__), exit(0)
#define dln()        fprintf(stderr,"\n")
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef double	  db;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI > VII;
typedef PR<int,int> PII;
typedef vector<PII> VPI;
const	int inf=2e9;
const	LL Inf=1e10;
const	int P=1e9+7;
const	int N=200005;

inline LL IN(){
	LL x = 0;
	int ch = 0, f = 0;
	for (CH; ch != -1 && (ch < 48 || ch > 57); CH) f = (ch == '-');
	for (; ch >= 48 && ch <= 57; CH) x = (x << 1) + (x << 3) + ch - '0';
	return f ? (-x) : x;
}
template<typename T> inline int chkmin(T &a, const T &b){if(b < a) return a = b, 1; return 0;}
template<typename T> inline int chkmax(T &a, const T &b){if(b > a) return a = b, 1; return 0;}

void renew(int &x, const int &y){
	x += y;
	if(x >= P) x -= P;
	if(x <  0) x += P;
}

int Pow(int x, int y, int p){
	int a = 1;
	for (; y; y >>= 1, x = (LL)x * x %p) if(y & 1) a=(LL)a * x%p;
	return a;
}

int n;
int mxd[N], sed[N], mad[N], gg[N], hev[N];
struct edge{
	int v, pre;
}e[N << 1]; int dex, adj[N];
int fa[N];

void dfs(int x){
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == fa[x]) continue;
		fa[v] = x;
		dfs(v);
		if(mxd[v] + 1 > mxd[x]){
			sed[x] = mxd[x];
			hev[x] = v;
			mxd[x] = mxd[v] + 1;
		}else
		if(mxd[v] + 1 > sed[x]){
			sed[x] = mxd[v] + 1;
		}
	}
}

void dp(int x){
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == fa[x]) continue;
		if(v == hev[x]){
			gg[v] = max(gg[x], sed[x]) + 1;
		}else{
			gg[v] = max(gg[x], mxd[x]) + 1;
		}
		dp(v);
	}
}

int hg[N], lo[N];
LL ans = 1;
char s[N];

void work(int x, int par){
	mad[x] = 0;
	if(s[x] == '1') lo[x] = 0; else lo[x] = 1 << 30;
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == par) continue;
		work(v, x);
		mad[x] = max(mad[x], mad[v] + 1);
		lo[x] = min(lo[x], lo[v] - 1);
	}
	hg[x] = min(mad[x] + 1, mxd[x] - 1);
	ans += max(0, hg[x] - lo[x] + 1);
	lo[x] = max(lo[x], hg[x] + 1);
	if(lo[x] == mxd[x]) lo[x] = 1 << 30;
}

int main(){
	scanf("%d", &n);
	REP(i, 1, n - 1){
		int x, y;
		scanf("%d%d", &x, &y);
		e[++dex] = (edge){y, adj[x]}; adj[x] = dex;
		e[++dex] = (edge){x, adj[y]}; adj[y] = dex;
	}
	dfs(1);
	dp(1);
	REP(i, 1, n) mxd[i] = max(mxd[i], gg[i]);
	int rt = min_element(mxd + 1, mxd + n + 1) - mxd;
	scanf("%s", s + 1);
	work(rt, 0);
	cout << ans << endl;
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:119:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:122:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^
./Main.cpp:130:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s + 1);
                    ^

Judge Result