您现在的位置是：首页 >学无止境 >时间戳优化网站首页学无止境

题意

给定一颗有根树，起初点全为白色，序列$a[i]$表示在第$i$秒将$a[i]$染成黑色，求在每次染色后有多少颗子树中既有黑色又有白色节点。

  
    int n;
    cin >> n;
    vector<int> mn(n + 1), mx(n + 1);
    vector<vector<int>> g(n + 1);
    for(int i = 2, x; i <= n; i++) {
        cin >> x;
        g[x].pb(i);
    }
    for(int i = 1; i <= n; i++) {
        int x; 
        cin >> x;
        mn[x] = mx[x] = i;
    }

    function<void(int)> dfs = [&](int x) {
        for(int y : g[x]) {
            dfs(y);
            mn[x] = min(mn[x], mn[y]);
            mx[x] = max(mx[x], mx[y]);
        }
    };
    dfs(1);
    //编号为i的点的子树内在[mn[i], mx[i] - 1]的时间内为斑马子树
    // for(int i = 1; i <= n; i++) DD(mn[i], mx[i]);
    vector<int> sum(n + 1);
    for(int i = 1; i <= n; i++) {
        sum[mn[i]]++;
        sum[mx[i]]--;
    }
    for(int i = 1; i <= n; i++) {
        sum[i] += sum[i - 1];
        cout << sum[i] << ' ';
    }