2021CCPC 哈尔滨站 C题Colorful Tree （树上dp+树上启发式合并）

传送门

就是这题，让我与金牌失之交臂

/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https://www.cnblogs.com/Knowledge-Pig/ 
************************************************************************/

#include
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 1e5 + 10;
int n, a[maxx], f[maxx], sz[maxx], id[maxx], add[maxx], mini[maxx], cnt = 0;
vector e[maxx];
bool cmp(pair A, pair B){
    if(A.second == B.second) return A.first > B.first;
    return A.second < B.second;
}
map dp[maxx];

void dfs(int u){
    int son = 0;
    sz[u] = 1;
    for(auto v : e[u]){
        dfs(v);
        sz[u] += sz[v];
        if(sz[v] > sz[son]) son = v;
    }
    if(!son){ id[u] = ++cnt; dp[cnt][a[u]] = 1; mini[cnt] = 1; }
    else{
        id[u] = id[son];
        dp[id[u]][0] = mini[id[u]];
        for(auto v : e[u]){
            if(v == son) continue;
            int y = mini[id[v]] + add[id[v]];
            for(auto tmp : dp[id[v]]){
                if(tmp.first == 0) continue;
                if(dp[id[u]].count(tmp.first)){
                    dp[id[u]][tmp.first] = min(dp[id[u]][tmp.first], dp[id[u]][0] + 1);
                    dp[id[u]][tmp.first] += min(tmp.second - 1 + add[id[v]], y)  - y;
                }
                else dp[id[u]][tmp.first] = tmp.second + add[id[v]] + dp[id[u]][0] - y;
                mini[id[u]] = min(mini[id[u]], dp[id[u]][tmp.first]);
            }
            add[id[u]] += y;
        }
    }

}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out","w", stdout);
#endif
    cin >> n;
    for(int i = 2; i <= n; ++i){
        cin >> f[i];
        e[f[i]].push_back(i);
    }
    for(int i = 1; i <= n; ++i) cin >> a[i];
    dfs(1);
    cout << mini[id[1]] + add[id[1]] << endl;
    return 0;
}
/*
20
1 2 3 4 4 1 2 3 8 3 3 8 6 4 2 1 15 6 14
0 0 0 0 18 0 13 0 3 2 11 18 4 0 0 2 13 20 2 18
*/