Div. 1 + Div. 2 Codeforces Round #831 A-E( 二 ) _生活百科

\(dp[u][1]\) 时，由于根节点 \(u\) 最后只可能等于一个子节点 \(v_i\)，那么 \(u\) 只可能衔接在一个 \(dp[v_i][1]\) 后面。
\(dp[v_i][0]\) 不能考虑进去。因为，当 \(v_i\) 为根的子树不是条链，一定存在子孙 \(w\) 使得 \(a[v_i]<a[w]\)，那么 \(a[u]<a[w]\) 不可能衔接到 \(w\) 后面；当 \(v_i\) 为根的子树是链时，则 \(dp[v_i][1] = dp[v_i][0]+1>dp[v_i][0]\)，没必要选。

时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码

#include <bits/stdc++.h>using namespace std;vector<int> g[100007];int f[100007][2];void dfs(int u) {f[u][0] = 0;f[u][1] = 1;for (auto v : g[u]) {dfs(v);f[u][0] += max(f[v][0], f[v][1]);f[u][1] = max(f[u][1], f[v][1] + 1);}}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;cin >> n;for (int i = 2;i <= n;i++) {int p;cin >> p;g[p].push_back(i);}dfs(1);cout << max(f[1][0], f[1][1]) << '\n';return 0;}