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

时间戳优化

jangyi. 2024-06-17 11:26:41
简介时间戳优化

题意

给定一颗有根树,起初点全为白色,序列 a [ i ] a[i] a[i]表示在第 i i i秒将 a [ i ] a[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] << ' ';
    }

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。