C++ 解法, 执行用时: 4305ms, 内存消耗: 51824K, 提交时间: 2021-11-11 03:50:55

#include <bits/stdc++.h>
 
const int maxn = 2e4 + 13;
 
int n, p[maxn], c[maxn], dfn, dl[maxn], dll[maxn], dlr[maxn];
std::vector<int> E[maxn];
std::bitset<maxn> e[maxn];
 
void dfs(int u) {
    dll[u] = dfn;
    dl[dfn++] = u;
    for(auto &&v : E[u]) {
        dfs(v);
    }
    dlr[u] = dfn;
}
 
int a[maxn], l, cc[maxn];
void addNode(int u) {
    l = 0;
    for(int r = dlr[u], i = dll[u]; i < r; ++i) {
        a[l++] = c[dl[i]];
    }
    for(int i = 0; i < l; ++i) {
        cc[a[i]] += 1;
    }
    for(int i = 0; i < l; ++i) {
        if(cc[a[i]]) {
            int w = a[i] * cc[a[i]];
            if(w <= n + 1) {
                e[w].set(u);
            }
            cc[a[i]] = 0;
        }
    }
}
 
int utoc[maxn], cedge[maxn];
 
bool match(int color) {
    cedge[color] += 1;
    for(int &value = cedge[color]; value <= n; value += 1) {
        if(!e[color][value])
            continue;
        if(!utoc[value] || match(utoc[value])) {
            utoc[value] = color;
            return true;
        }
    }
    return false;
}
 
int main() {
    scanf("%d", &n);
    for(int i = 2; i <= n; ++i) {
        scanf("%d", p + i);
        E[p[i]].push_back(i);
    }
    for(int i = 1; i <= n; ++i) {
        scanf("%d", c + i);
    }
    dfs(1);
    for(int i = 1; i <= n; ++i) {
        e[0].set(i);
        addNode(i);
    }
    int ans = 1;
    for(int i = 1; i < n; ++i) {
        if(!match(i)) {
            break;
        }
        ans += 1;
    }
    printf("%d\n", ans);
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 7253ms, 内存消耗: 51716K, 提交时间: 2023-05-03 15:00:56

#include <bits/stdc++.h>
#define maxn 20010
using namespace std;
 
int n,x;
int c[maxn];
vector<int> v[maxn];
bitset<maxn> bs[maxn];
vector<int> vv;
int cnt[maxn];
 
void dfs(int i)
{
    vv.push_back(c[i]);
    for(int j = 0;j < v[i].size();j++) dfs(v[i][j]);
}
 
int tag[maxn], to[maxn], nxt[maxn];
 
bool match(register int i)
{
    tag[i] = x, nxt[i]++;
    for(register int &j = nxt[i];j <= n;j++)
    {
        if(bs[i][j]   &&  (!to[j] || (tag[to[j]] != x && match(to[j])) ) )
        {
            to[j] = i;
            return true;
        }
    }
    return false;
}
 
int main()
{
    scanf("%d", &n);
    int i,j;
    for(i=2;i<=n;i++)
    {
        scanf("%d", &x);
        v[x].push_back(i);
    }
    for(i=1;i<=n;i++) scanf("%d", &c[i]);
    for(i=1;i<=n;i++)
    {
        dfs(i);
        for(j=0;j<vv.size();j++)
        {
        	cnt[vv[j]]++;
		}
		for(j=0;j<vv.size();j++)
        {
			if(cnt[vv[j]] && cnt[vv[j]] * vv[j] < n)
                bs[cnt[vv[j]] * vv[j]][i] = 1;
			cnt[vv[j]] = 0;
		}
		vv.clear();
    }
    for(i=1;i<n;i++)
    {
        x = i;
        if(match(i)==0)
        {
            return printf("%d",i)  ,0;
        }
    }
    printf("%d",n);
}

C++14(g++5.4) 解法, 执行用时: 7134ms, 内存消耗: 52000K, 提交时间: 2020-07-28 00:38:03

#include <bits/stdc++.h>
#define maxn 20086
 
using namespace std;
 
int n, x;
int c[maxn];
vector<int> v[maxn];
bitset<maxn> bs[maxn];
 
vector<int> vv;
int cnt[maxn];
 
void dfs(int i){
    vv.push_back(c[i]);
    for(int j = 0;j < v[i].size();j++) dfs(v[i][j]);
}
 
int tag[maxn], to[maxn], nxt[maxn];
 
bool match(register int i){
    tag[i] = x, nxt[i]++;
    for(register int &j = nxt[i];j <= n;j++){
        if(bs[i][j] && (!to[j] || (tag[to[j]] != x && match(to[j])))){
            to[j] = i;
            return true;
        }
    }
    return false;
}
 
int main(){
    scanf("%d", &n);
    for(int i = 2;i <= n;i++){
        scanf("%d", &x);
        v[x].push_back(i);
    }
    for(int i = 1;i <= n;i++) scanf("%d", &c[i]);
    for(int i = 1;i <= n;i++){
        dfs(i);
        for(int j = 0;j < vv.size();j++){
        	cnt[vv[j]]++;
		}
		for(int j = 0;j < vv.size();j++){
			if(cnt[vv[j]] && cnt[vv[j]] * vv[j] < n) bs[cnt[vv[j]] * vv[j]][i] = 1;
			cnt[vv[j]] = 0;
		}
		vv.clear();
    }
    for(int i = 1;i < n;i++){
        x = i;
        if(!match(i)){
            return printf("%d", i), 0;
        }
    }
    printf("%d", n);
}