J – Mex Tree

题目描述：

给你一颗树，一共n个节点，n-1条边，点的编号为1到n

每个点都有一个权值ai，n个点的权值是0到n-1的一个全排列

现在需要输出n+1个数字，对于第i个数字，我们需要输出满足mex{a[j]}=i,j属于所选连通子图的点的最大的连通子图的数量

思路：

mex指的是未出现过的最小的正整数，所以对于第i个答案，我们需要找到包含0到i-1所有权值的点，且不含i权值的点，所以我们对于每个询问，我们找到权值i对应的点，把他从图上扣掉后，树会被分成若干个联通子图(子树+父亲)，只有当某个联通子图包含了0到i-1的所有点才是符合条件的，我们可以通过维护集合的最小值来判断，子树的最小值很好维护，dfs的时候就能维护出来，难的是维护树中除了这个点及其所有子树外剩下所有节点权值的最小值，这个可以用跑出dfs序后用st表来维护

只有当权值为i的点扣掉后的所有联通子图中只存在一个子图的最小值是0，且其他子图的最小值都大于i，则答案是最小值是0的子树的大小，否则就是0

对于i=n时，答案就是n，不用计算

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1000000 + 50
int n, m, k, x;
int tr[MAX];
int root;
vector<int>G[MAX];
int num[MAX];
int ar[MAX];
int id[MAX];
int dfs(int u, int fa){
    num[u] = 1;
    ar[++m] = u;
    id[u] = m;
//    fuck[tr[u]] = m;
    for(auto v : G[u]){
        if(v == fa)continue;
        num[u] += dfs(v, u);
    }
    return num[u];
}

int st_min[MAX][22];
int lg[MAX];
void init(){
    for(int i = 1; i <= n; ++i) st_min[i][0] = ar[i];
    lg[1] = 0;
    for(int i = 2; i <= n; ++i)lg[i] = lg[i / 2] + 1;
    for(int j = 1; j <= lg[n]; ++j){
        for(int i = 1; i + (1 << j) - 1 <= n; ++i){
            st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1<<(j - 1))][j - 1]);
        }
    }
}
int get_st_min(int l, int r){
    if(l > r)return inf;
    int d = lg[r - l + 1];
    return min(st_min[l][d], st_min[r - (1<<d) + 1][d]);
}
int ans[MAX];
int fuck(int u, int fa){
    int minx = u;
    vector<pii>shit;
    for(auto v : G[u]){
        if(v == fa)continue;
        int x = fuck(v, u);
        shit.push_back(m_p(x, num[v]));
        minx = min(minx, x);
    }
    if(u != root){
        int a = id[u] - 1;
        int b = id[u] + num[u];
        int cao = min(get_st_min(1, a), get_st_min(b, n));
        shit.push_back(m_p(cao, n-num[u]));
    }
    int p = (u == 0 ? 1 : 0);
    sort(shit.begin(), shit.end());
    if(shit.size() == 1){
        if(shit.front().first == p)ans[u] = shit.front().second;
        else ans[u] = 0;
    }
    else{
        if(shit.front().first == p && shit[1].first > u)ans[u] = shit.front().second;
        else ans[u] = 0;
    }
    return minx;
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
    }
    if(n == 1){
        cout << 0 << ' ' << 1 << endl;
        return;
    }
    root = tr[1];
    for(int i = 2; i <= n; ++i){
        cin >> x;
        G[tr[x]].push_back(tr[i]);
        G[tr[i]].push_back(tr[x]);
    }
    dfs(tr[1], -1);
    init();
    fuck(tr[1], -1);
    ans[n] = n;
    for(int i = 0; i <= n; ++i){
        cout << ans[i] << ' ';
    }
    cout << endl;
}


int main(){
    io;
    work();
    return 0;
}