(思维/顺序) Christmas Spruce CodeForces – 913B

传送门：http://codeforces.com/problemset/problem/913/B
* **题意：** 给一颗n个结点的树（结点1默认存在且至少有两个子结点），（输入当前结点的父结点）计算这棵树是否是每个结点都有三个以上的空结点，是的话Yes。
* **题解：** 因为n号结点总是在n-1号结点后面或者与n-1号结点无关（不在同一子树中），所以只要按逆序将n号结点对前面的影响计算出并减去即可。

WA了很多次，主要是只记得将影响减去而忘记考虑影响减去之后对单子结点类结点的影响；

代码：

#include<cstdio>
using namespace std; 


struct tree{
	int pa;
	int cnt;
	int si;
}t[1005];

int count(int sign){
	if(sign == 0) return 1;      //到最后 
	int k = t[sign].cnt;//子结点数
	if(k >= 3){
		t[t[sign].pa].cnt -= 1;
	}else if(k == 0){
		if(t[sign].si == 1){//该结点有子树但在前面计算影响的时候被减去了（前面子树满足条件则减去）
			return 0;
		}
	}
	else{
		return 0;
	}
	count(sign - 1);
}


int main(){
	int n;
	scanf("%d", &n);
	for(int i = 1;i <= n; i++){
		t[i].cnt = 0;
		t[i].si = 0;
	}
	t[1].pa = 0;
	int p;
	for(int i = 2; i <=n; i++){
		scanf("%d", &p);//输入父结点 
		t[i].pa = p;//父结点赋值 
		t[p].cnt++;//父结点的空结点数加一 
		t[p].si = 1;
	}
	if(count(n)){
		printf("Yes");
	}else{
		printf("No");
	}
	
	return 0;
}