CF 551 D.Serval and Rooted Tree 树形DP

传送门：http://codeforces.com/contest/1153/problem/D

思路：

这道题想了一天，突发奇想，就是维护每个点两个值，第几大和第几小，就可以有传递性了。

#include <bits/stdc++.h>using namespace std;#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
const ll inff = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;        const int maxn = 3e5+;
        int a[maxn];
        vector<int>mp[maxn];
        int dp[maxn][];
        int all = ;
        void dfs(int u, int fa) {
            if(mp[u].size() == ) dp[u][] = dp[u][] = , all++;
            else if(a[u] == ) dp[u][] = , dp[u][] = inf;
            else if(a[u] == ) dp[u][] = inf, dp[u][] = ;            for(int i=; i<mp[u].size(); i++) {
                int v = mp[u][i];
                if(v == fa) continue;
                dfs(v, u);                if(a[u] == ) {
                    dp[u][] = min(dp[v][], dp[u][]);
                    dp[u][] += dp[v][];
                }
                else {
                    dp[u][] += dp[v][];
                    dp[u][] = min(dp[v][], dp[v][]);
                }
            }
        }int main(){
        int n;
        scanf("%d", &n);
        for(int i=; i<=n; i++) scanf("%d", &a[i]);
        for(int i=; i<=n; i++) {
            int x;  scanf("%d", &x);
            mp[x].pb(i);
        }
        memset(dp, inf, sizeof(dp));
        dfs(, );
       // cout<<" dp[5][1] = " <<dp[5][1]<<endl;
       // cout<<dp[1][0] << " , " << dp[1][1]<<endl;
        printf("%d\n", max(dp[][], all - dp[][] +  ));
        return ;
}