G Greetings Souvenir

再更新一下，造了一些hack数据对拍，拿了三份代码对拍，给出几份hack数据
输出彼此之间都有一致的数据也有不一致的，说明至少四支队伍可以hack掉三只队伍!!!!

6
1 2 1 2 5
6 5 2 1 2 3
顶不住也给我顶：6
空白：5
吃顿好的：6
ContestinSurgery ：段错误

6
6 4 5 2 1
3 1 6 2 5 4
顶不住也给我顶：4
空白：6
吃顿好的：6
ContestinSurgery ：段错误

8
1 2 2 2 2 1 7
3 2 7 3 2 3 5 1
顶不住也给我顶：6
空白：6
吃顿好的：8
ContestinSurgery ：段错误

网络流(不会) or 真正理解匈牙利算法
给出一个也许正确的做法，因为它确实AC了
(应该是假算法了，就是数据弱了让我这个渣渣跑过去了)

这里建出来的二分图的特殊性质就是，越相邻的两个节点的bitset越相似，一个节点的父节点和子节点至多有两位不同（父节点颜色对应的值增加上了该颜色），也许导致这个算法的正确几率显著提升？或者完全正确？

这里匈牙利是n^2的，做了个（错误的）优化，每个左部点会记录已经匹配到的最小右部点
可以发现复杂度是o(边数)的
然而这样就假了(不是图论选手啊我)，但是他就是AC了，也许建出来的图具有有某些性质？？？，也许数据弱了？

给出一个图论队友给的hack数据来hack匹配部分，这里mex应该是4，输出了3

#include<bits/stdc++.h>
using namespace std;
#define ul unsigned long
const int maxn=32;
bitset<maxn> b[maxn];
int c[maxn],n;

int p[maxn];
int r[maxn];
int find(int x){
    for(int i=r[x]+1;i<=n;i++){
        r[x]=i;
        if(!b[i][x])continue;
        if(!p[i]||find(p[i])){
            p[i]=x;
            return 1;
        }
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    n=3;
    b[1][1]=1;
    b[1][2]=1;
    b[2][1]=1;
    b[2][2]=1;
    b[2][3]=1;
    b[3][1]=1;

    int ans=1;
    for(int i=1;i<n;i++){
        if(find(i))ans++;
        else break;
    }
    cout<<ans<<endl;

}

题意：n个点的一棵树，第i个节点有颜色ci，每个节点可以分配一个任意的值di，ei=子树内颜色为di的个数*di，求mex(e1,e2...en)的最大值

思路，n^2预处理出每个节点的可能值，用bitset储存，将节点的所有可能值1到(n-1)看做左部，节点1到n看做右部，n^2做类似匈牙利匹配(暴力匹配)，因为mex函数的集合要求数是连续的，所以我们逐个节点依次匹配，直到失配，总复杂度(n^2)，优于标程，但是还是跑了6.8秒。

其中mex函数中的0始终可以分配给一个数，所以只要最后答案不超过n就行啦

预处理bitset表示的二分图如果多个log很容易T，用map TLE妥妥的，改成vector就AC了。

#include<bits/stdc++.h>
using namespace std;
#define ul unsigned long
// const int maxn=32;
const int maxn=20032;
vector<int> e[maxn];
bitset<maxn> b[maxn];
int c[maxn],n;
void dfs(int u,vector<pair<int,int> > &mp){
    vector<pair<int,int> > now;
    now.push_back({c[u],1});
    for(auto &v:e[u]){
        dfs(v,now);
    }

    int tp[n+1]={};
    for(auto &it:mp){
        tp[it.first]=it.second;
    }
    for(auto &it:now){
        int tmp=it.first*it.second;
        if(tmp<n)b[u].set(tmp);
        tp[it.first]+=it.second;
    }
    mp.clear();
    for(int i=0;i<=n;i++){
        if(tp[i]){
            mp.push_back({i,tp[i]});
        }
    }
}
int p[maxn];
int r[maxn];
int find(int x){
    for(int i=r[x]+1;i<=n;i++){
        r[x]=i;
        if(!b[i][x])continue;
        if(!p[i]||find(p[i])){
            p[i]=x;
            return 1;
        }
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        int tmp;cin>>tmp;
        e[tmp].push_back(i);
    }
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }

    vector<pair<int,int> > now;
    dfs(1,now);

    int ans=1;
    for(int i=1;i<n;i++){
        if(find(i))ans++;
        else break;
    }
    cout<<ans<<endl;

}