# 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; } ```
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up