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 ;

}