Submission #1045131

---

Source Code Expand

#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

// for a given operation (x,d) that does not paint all vertices, determine the canonical of the operation as follows:
// * if there are at least two adjacent vertices of which not every descendant is painted, stop.
// * otherwise there is exactly one adjacent vertex of which not every descendant is painted, name it y.
//   - if operation (y,d-1) would paint the same vertices, go there
//   - otherwise, stop.
// -> the canonical operation paints the same vertices
// -> an operation is canonical iff:
// * it is adjacent to at least two not-fully painted subtrees AND (snuke likes the vertex OR a vertex in a fully painted adjacent subtree)
// * it is adjacent to exactly one not-fully painted subtree AND the other adjacent subtrees are (nearly) exactly fully painted AND (snuke likes the vertex OR a vertex in one of those fully painted subtrees)

const int MAXN=200000;
const int MAXM=MAXN-1;

int n;
int ghead[MAXN],gnxt[2*MAXM],gto[2*MAXM];
char slike[MAXN+1];

int par[MAXN];
int edepth[2*MAXM]; bool elike[2*MAXM];
int dmx[MAXN],dmxidx[MAXN],dmx2[MAXN]; int clike[MAXN],clike2[MAXN];

pair<int,bool> dfs1(int at) {
	pair<int,bool> ret=MP(0,slike[at]=='1'); dmx[at]=dmx2[at]=0,dmxidx[at]=-1,clike[at]=clike2[at]=-1;
	for(int x=ghead[at];x!=-1;x=gnxt[x]) {
		int to=gto[x];
		if(to==par[at]) continue;
		par[to]=at;
		pair<int,bool> cur=dfs1(to);
		edepth[x]=cur.first+1; elike[x]=cur.second;
		if(edepth[x]>ret.first) ret.first=edepth[x]; if(cur.second) ret.second=true;
		if(edepth[x]>dmx[at]) dmx2[at]=dmx[at],dmx[at]=edepth[x],dmxidx[at]=to; else if(edepth[x]>dmx2[at]) dmx2[at]=edepth[x];
		if(elike[x]) if(clike[at]==-1) clike[at]=to; else if(clike2[at]==-1) clike2[at]=to;
	}
	return ret;
}
void dfs2(int at) {
	for(int x=ghead[at];x!=-1;x=gnxt[x]) {
		int to=gto[x];
		if(to!=par[at]) continue;
		edepth[x]=(dmxidx[to]!=at?dmx[to]:dmx2[to])+1;
		elike[x]=slike[to]=='1'||clike[to]!=-1&&clike[to]!=at||clike2[to]!=-1;
		if(edepth[x]>dmx[at]) dmx2[at]=dmx[at],dmx[at]=edepth[x],dmxidx[at]=to; else if(edepth[x]>dmx2[at]) dmx2[at]=edepth[x];
		if(elike[x]) if(clike[at]==-1) clike[at]=to; else if(clike2[at]==-1) clike2[at]=to;
	}
	for(int x=ghead[at];x!=-1;x=gnxt[x]) {
		int to=gto[x];
		if(to==par[at]) continue;
		dfs2(to);
	}
}

void run() {
	scanf("%d",&n);
	REP(i,n) ghead[i]=-1;
	REP(i,n-1) {
		int a,b; scanf("%d%d",&a,&b); --a,--b;
		gnxt[2*i+0]=ghead[a]; ghead[a]=2*i+0; gto[2*i+0]=b;
		gnxt[2*i+1]=ghead[b]; ghead[b]=2*i+1; gto[2*i+1]=a;
	}
	scanf("%s",slike);

	par[0]=-1; dfs1(0); dfs2(0);
	//REP(i,n) printf("%d: [dmx=%d,dmxidx=%d,dmx2=%d][clike=%d,clike2=%d]\n",i,dmx[i],dmxidx[i],dmx2[i],clike[i],clike2[i]);
	//REP(x,2*(n-1)) printf("%d->%d: depth=%d like=%c\n",gto[x^1],gto[x],edepth[x],elike[x]?'V':'-');

	ll ret=1;
	REP(at,n) {
		int mnlike=INT_MAX; int mx=0,mx2=0;
		if(slike[at]=='1') mnlike=0;
		for(int x=ghead[at];x!=-1;x=gnxt[x]) {
			if(elike[x]&&edepth[x]<mnlike) mnlike=edepth[x];
			if(edepth[x]>mx) mx2=mx,mx=edepth[x]; else if(edepth[x]>mx2) mx2=edepth[x];
		}
		ll a=0,b=0;
		if(mnlike<=mx2-1) a+=mx2-1-mnlike+1;

		if(mnlike<=mx2&&mx2<=mx-1) b+=min(mx2+1,mx-1)-mx2+1; // mx2..min(mx2+1,mx-1)
		//printf("%d: %lld %lld [mnlike=%d,mx=%d,mx2=%d]\n",at,a,b,mnlike,mx,mx2);
		ret+=a+b;
	}
	printf("%lld\n",ret);
}

int main() {
	run();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void run()’:
./Main.cpp:85:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:88:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int a,b; scanf("%d%d",&a,&b); --a,--b;
                               ^
./Main.cpp:92:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",slike);
                   ^

Judge Result