---
# System prepended metadata

title: tcirc d107 樹的最大獨立集

---

# tcirc d107 樹的最大獨立集

https://judge.tcirc.tw/ShowProblem?problemid=d107

* 最大獨立集一定包含葉節點，因為如果選葉節點的父節點，也一定可以選此葉節點，而每一層葉節點的數量一定大於或等於其父節點的數量
* 一個點可以取也取決於其子節點是否都不能取，所以用and

```cpp=
#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

vector<int> p[100005];
bool chosen[100005]={0};
LL ans=0;

bool dfs(int v){
	bool choose=1;
	for(auto a:p[v]){
		choose&=dfs(a);
	}
	if(choose) ans++;
	return !choose;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, a;
	cin>>n;
	rep(i,1,n){
		cin>>a;
		p[a].EB(i);
	}
	dfs(0);
	cout << ans << NL;
}

```