The 2023 ICPC Asia Nanjing Regional Contest

2023/11/24 ICPC Competition

---

qoj補題鏈接

第一次區域賽，也是成功打鐵簽到，飯堂很好，袋鼠也很可愛。

---

I. Counter

I. 概述

有一個計數器進行了 $n$ 次操作，初始為 $0$，每次操作可以 $+1$ 或者設爲 $0$。給定 $m$ 個位置的狀態，判斷狀態是否可行。
n ~ 1e9
m ~ 1e5

考慮兩個相鄰的狀態 $a_i,a_j$ ，如果轉移中其中一個操作設$0$了，那下一個狀態只能在 $[0, j-i)$ 中，反之下一個狀態必須為 $a_i+j-i$ 。（就簽了這題）

複雜度 $O(mlogm)$。

I. 代碼

#include "bits/stdc++.h"
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
#define INF 0x3f3f3f3f
#define LNF (ll) 0x3f3f3f3f3f3f3f3f 
 
#define maxm 100010

pii v[maxm];

void solve() {
    int n, m; cin >> n >> m;
 
    for (int i = 1; i <= m; ++ i) cin >> v[i].first >> v[i].second;
    sort(v, v+m+1);

    for (int i = 0; i < m; ++ i) {
        int mx = v[i].second + (v[i+1].first - v[i].first);
        int md = max(v[i+1].first - v[i].first - 1, 0);
 
        if (v[i+1].second == mx || v[i+1].second <= md) continue;
        cout << "No" << '\n';
        return;
    }
    cout << "Yes" << '\n';
}
 
int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t --) solve();
    return 0;
}

---

C. Primitive Root

C. 概述

給定 $p$ 和 $m$，求滿足 $g\leq m$ 且 $g \oplus (p-1) \equiv 1\ (mod\ p)$ 的整數個數。
p ~ 1e18
m ~ 1e18

注意到 $[2^k,\ 2^{k+1})$ 這個區間與某數的異或是連續的（因爲00..00和11..11之間的異或互補），所以我們可以把 $m$ 的最低位拆成 $[m\And (m-1),\ m)$ 這個區間，除法算一下這個區間有多少個異或是滿足條件的，全部加起來就是答案（特判一下 $m$）。顯然這樣的區間只能拆出 $logm$ 個。

複雜度是 $O(logm)$ 。

C. 代碼

#include "bits/stdc++.h"
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
#define INF 0x3f3f3f3f
#define LNF (ll) 0x3f3f3f3f3f3f3f3f 
 
ll cnt(ll l, ll r, ll m) { // [l, r]
    if (l % m != 1) l = (l + m - 1) / m * m + 1;
    if (r - l < 0) return 0;
    return 1 + (r - l) / m;
}
 
void solve() {
    ll p, m;
    cin >> p >> m;
 
    ll res = (m ^ (p-1)) % p == 1;
    for (int i = 0; i < 64; ++ i) {
        if (!(m & (1ll << i))) continue;
        ll pfx = ((m - (1ll << i)) ^ (p-1)) >> i << i;
        ll mx = pfx + (1ll << i) - 1;
        ll mn = pfx;
 
        res += cnt(mn, mx, p);
        m &= m-1;
    }
    cout << res << '\n';
}
 
int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t --) solve();
    return 0;
}

---

G. Knapsack

G. 概述

有 $n$ 個物品和 $W$ 的本金，每個物品有 $w$ 的價格和 $v$ 的價值，可以選其中 $k$ 個免費獲取，求最大價值和。
n ~ 1e3
W ~ 1e4
v ~ 1e9

考慮最優解中一些是買的一些是免費獲取的，那麽所有免費獲取的價格都不低於買的，否則可以跟買的交換獲取相同的價值同時使用更少的本金。而如果兩者有一些物品的價格是相等的，這些物品可以相互交換而不影響結果。所以如果把物品按 $w$ 排序，必然存在分割使得左邊包含了最優解中所有買的物品，右邊包含了最優解中所有免費獲取的物品。左邊買的用背包求，右邊拿前 $k$ 大，每個分割點都算一下。

複雜度是 $O(nW + nlogn)$。

G. 代碼

#include "bits/stdc++.h"
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
#define INF 0x3f3f3f3f
#define LNF (ll) 0x3f3f3f3f3f3f3f3f 
 
#define maxn 5010
#define maxw 10010
 
struct item {
    int w, v;
} a[maxn];
 
ll sum[maxn], dp[maxw];
 
void solve() {
    int n, W, k; cin >> n >> W >> k;
 
    for (int i = 0; i < n; ++ i) cin >> a[i].w >> a[i].v;
    sort(a, a+n, [&](auto& x, auto& y) {
        return x.w < y.w;
    });
 
    priority_queue<int, vector<int>, greater<int>> pq;
    ll csum = 0;
    for (int i = n-1; i >= 0; -- i) {
        if (k == 0) continue;
        if (pq.size() < k) {
            csum += a[i].v;
            pq.push(a[i].v);
        } else if (pq.top() < a[i].v) {
            csum += a[i].v - pq.top();
            pq.pop();
            pq.push(a[i].v);
        }
        sum[i] = csum;
    }
 
    ll res = sum[0];
    for (int i = 0; i < n; ++ i) {
        for (int j = W; j >= a[i].w; -- j) {
            dp[j] = max(dp[j], dp[j - a[i].w] + a[i].v);
        }
        res = max(res, *max_element(dp, dp+W+1) + sum[i+1]);  
    }
    cout << res << '\n';
}
 
int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; t = 1;
    while (t --) solve();
    return 0;
}

---

F. Equivalent Rewriting

F. 概述

有一個長度為 $m$，初始為 $0$ 的數組。給定 $n$ 個操作，每個操作會把數組的 $p$ 個下標的值改成當前操作的序號，問是否存在不同的操作排列可以得到與順序操作一樣的結果。
n ~ 1e5
m ~ 1e5

先模擬一下順序操作，考慮某個下標 $i$ 的值是 $v$，那麽需要保證第 $v$ 個操作是所有涉及下標 $i$ 的操作中最後進行的。我們顯然可以建立一個拓撲序然後拓撲排序求解，當隊列或者堆存在多於一個元素時有解，可以任選執行順序（這裏選擇倒序），否則無解。

複雜度是 $O(\sum p + nlogn)$。

F. 代碼

#include "bits/stdc++.h"
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
#define INF 0x3f3f3f3f
#define LNF (ll) 0x3f3f3f3f3f3f3f3f 
 
#define maxn 100010
 
vector<int> op[maxn];
int seq[maxn];
 
int ind[maxn];
vector<int> G[maxn];

void solve() {
    int n, m; cin >> n >> m;
 
    for (int i = 1; i <= n; ++ i) op[i].clear(), G[i].clear(), ind[i] = 0;
    for (int i = 1; i <= m; ++ i) seq[i] = 0;
 
    for (int i = 1; i <= n; ++ i) {
        int p; cin >> p;
        for (int j = 0; j < p; ++ j) {
            int b; cin >> b;
            op[i].emplace_back(b);
            seq[b] = i;
        }
    }
  
    for (int i = 1; i <= n; ++ i) {
        for (auto& b : op[i]) {
            if (seq[b] && seq[b] != i) {
                G[i].emplace_back(seq[b]);
                ind[seq[b]] ++;
            }
        }
    }
  
    vector<int> q;
    for (int i = 1; i <= n; ++ i) if (!ind[i]) q.emplace_back(i);
 
    bool f = 0;
    vector<int> res;
 
    while (!q.empty()) {
        if (!f && q.size() > 1) {
            f = 1;
            sort(q.begin(), q.end());
        }
 
        int u = q.back(); q.pop_back();
        res.emplace_back(u);
 
        for (auto& v : G[u]) if (!-- ind[v]) q.emplace_back(v);
    }
 
    if (f) {
        cout << "Yes" << '\n';
        for (int i = 0; i < res.size(); ++ i) cout << (i == 0 ? "" : " ") << res[i];
        cout << '\n';
    } else {
        cout << "No" << '\n';
    }
}
 
int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t --) solve();
    return 0;
}

---

A. Cool, It’s Yesterday Four Times More

A. 概述

有一個 $n * m$ 的網格，上面填滿了袋鼠和洞。有上下左右四種操作，會把所有場上的袋鼠向對應方向移動一格，移動到洞或者網格外袋鼠會消失。對於每只袋鼠，問是否存在操作方案使得其他袋鼠消失。
n ~ 1e3
m ~ 1e3
n * m ~ 1e3

注意到（其實沒注意到，看題解的）可以枚舉兩隻袋鼠的位置，考慮 $f(i, j, x, y)$ 表示位置在 $i,j$ 的袋鼠能把位置在 $x,y$ 的袋鼠送走，終止狀態是 $i,j$ 在網格内且不是洞而 $x,y$ 在網格外或者是洞，可以選擇枚舉每個終止狀態進行 $dfs$ 或者多源 $bfs$ 求解 $f$。然後對於每隻袋鼠，枚舉是否能送走其他袋鼠。

複雜度是 $O((nm)^2)$。

A. 代碼

#include "bits/stdc++.h"
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
#define INF 0x3f3f3f3f
#define LNF (ll) 0x3f3f3f3f3f3f3f3f 
 
#define maxn 1010

int n, m;
bool vld[maxn][maxn];
bool vis[150 * maxn * maxn];

bool out(int i, int j) {
    return i < 0 || j < 0 || i > n + 1 || j > m + 1;
}

int id(int i, int j) {
    return i * (m + 5) + j;
}

int id(int i, int j, int x, int y) {
    return id(i, j) * (n + 5) * (m + 5) + id(x, y);
}

using ti4 = tuple<int, int, int, int>;

void solve() {
    cin >> n >> m;

    for (int i = 0; i <= n + 1; ++ i) {
        for (int j = 0; j <= m + 1; ++ j) {
            vld[i][j] = 0;
            for (int x = 0; x <= n + 1; ++ x) {
                for (int y = 0; y <= m + 1; ++ y) {
                    vis[id(i, j, x, y)] = 0;
                }
            }
        } 
    }

    for (int i = 1; i <= n; ++ i) {
        string s; cin >> s;
        for (int j = 1; j <= m; ++ j) {
            vld[i][j] = s[j - 1] == '.' ? 1 : 0;
        }
    }

    queue<ti4> q;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            if (!vld[i][j]) continue;

            for (int x = 0; x <= n + 1; ++ x) {
                for (int y = 0; y <= m + 1; ++ y) {
                    if (vld[x][y]) continue;
  
                    vis[id(i, j, x, y)] = 1;
                    q.push(ti4(i, j, x, y));
                }
            }
        }
    }

    while (!q.empty()) {
        auto [ci, cj, cx, cy] = q.front(); q.pop();
  
        int d[] = { -1, 0, 1, 0, -1 };
        for (int i = 0; i < 4; ++ i) {
            int dx = d[i], dy = d[i+1];
            auto [ni, nj, nx, ny] = ti4(ci+dx, cj+dy, cx+dx, cy+dy);

            if (out(ni, nj) || out(nx, ny) || !vld[ni][nj] || vis[id(ni, nj, nx, ny)]) continue;
            vis[id(ni, nj, nx, ny)] = 1;
            q.push(ti4(ni, nj, nx, ny));
        }
    }

    int res = 0;
    for (int i = 1; i <= n; ++ i ) {
        for (int j = 1; j <= m; ++ j) {
            if (!vld[i][j]) continue;

            bool f = 1;
            for (int x = 1; x <= n; ++ x) {
                for (int y = 1; y <= m; ++ y) {
                    if (i == x && j == y) continue;
                    if (!vld[i][j]) continue;

                    f &= vis[id(i, j, x, y)];
                }
            }
            res += f;
        }
    }
    cout << res << '\n';
}
 
int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t --) solve();
    return 0;
}

L. Elevator

L. 概述

有 $n$ 組包裹，每組有一個目標樓層 $f$ 和 $c$ 個等重且重量為 $1$ 或 $2$ 的貨物。有一架可以承載偶數重量 $k$ 的電梯，每次可以用 $F$ 的成本把裝載的目標樓層在 $[0, F]$ 的貨物送達。求把所有貨物送到其目標樓層的最小成本。
n ~ 1e5
k ~ 2e10
c ~ 1e5
f ~ 1e5

考慮所有貨物重量為 $1$ 時以 $f$ 的倒序排列分組最優。可以想到（不會證明）以 $f$ 的倒序貪心分組。由於會出現存在連續貨物不能填滿的情況（重量和為奇數而當前貨物重量為 $2$），要貪心選取 $f$ 最大且重量為 $1$ 的貨物填充。

因爲 $k$ 比較大所以枚舉包裹時要分兩種情況處理：

1. 把貨物放到上一架電梯裏，如果能全部放完就去一下組，這樣不用算代價（上一組已經算了）。
2. 以電梯爲單位分拆貨物，必然可以拆分出 $m$ 組填滿電梯的組（因爲k是偶數可以被 $1$ 或者 $2$ 整除），剩餘的開一架沒填滿的電梯，要把這部電梯的代價也算進來。

複雜度是 $O(nlogn)$。

L. 代碼

#include "bits/stdc++.h"
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
#define INF 0x3f3f3f3f
#define LNF (ll) 0x3f3f3f3f3f3f3f3f 
 
#define maxn 100010

struct group {
    ll c, w, f;
} g[maxn];

void solve() {
    ll n, k; cin >> n >> k;

    for (int i = 0; i < n; ++ i) cin >> g[i].c >> g[i].w >> g[i].f;
    sort(g, g+n, [&](auto& x, auto& y) {
        return x.f > y.f;
    });

    ll rem = 0, res = 0;
    int j = 0;

    auto rmnxt = [&](int i) {
        j = max(j, i);
        while (j < n && (!g[j].c || g[j].w != 1)) ++ j;
        if (j < n) g[j].c --;
    };

    for (int i = 0; i < n; ++ i) {
        ll rc = min(g[i].c, rem / g[i].w);
        rem -= rc * g[i].w;
        g[i].c -= rc;
        if (rem == 1) rmnxt(i + 1), rem = 0;

        if (!g[i].c) continue;

        ll kc = g[i].c * g[i].w / k;
        ll rst = g[i].c * g[i].w % k;
        res += (kc + (rst > 0)) * g[i].f;
        rem = (k - rst) % k;
        if (rem == 1) rmnxt(i + 1), rem = 0;
    }

    cout << res << '\n';
}
 
int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t --) solve();
    return 0;
}

---

M. Trapping Rain Water

M. 概述

給定一個長度為 $n$ 的數組 $a$，有 $q$ 次增加數值的修改，每次修改后求 $\sum_{i=1}^n (min(f_i,\ g_i) - a_i)$，其中 $f$ 是前綴最大值，$g$ 是後綴最大值。
n ~ 1e5
q ~ 1e6

注意到 $min(f_i,\ g_i) = f_i + g_i - max(f_i,\ g_i) = f_i + g_i - max(a)$ ，考慮分別維護 $f$ 和 $g$。由於 $a$ 的值只會增加且 $f/g$ 是單調的，所以我們可以暴力維護一些 $f/g$ 值相等的區間，每次修改把對應區間拆分然後合并後面值更小的所有區間，過程中維護一下他們的和就可以了。區間可以用 $set$ 來維護。 $set$ 中最多有 $n$ 個元素，每次拆分最多把區間數 $+1$，每次合并區間數 $-1$，所以拆分和合并的次數不會超過 $q+n$。

複雜度是 $O((n+q)logn)$。

M. 代碼

#include "bits/stdc++.h"
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
#define INF 0x3f3f3f3f
#define LNF (ll) 0x3f3f3f3f3f3f3f3f 
 
#define maxn 100010

struct interval {
    int l, r;
    ll a;

    ll eval() const {
        return 1ll * (r - l) * a;
    }

    bool operator < (const interval& o) const {
        return r < o.r;
    }
};

set<interval> fs, gs;
ll sa, sf, sg;
ll a[maxn];

void ins_fs(int idx, ll v) {
    auto it = fs.lower_bound({ idx, idx + 1, v });
    if (it->a >= v) return;

    interval l = { it->l, idx, it->a };
    interval r = { idx, it->r, v };

    for (; it->a <= v; it = fs.erase(it)) r.r = it->r, sf -= it->eval();
    if (l.l != l.r) fs.insert(l), sf += l.eval();
    if (r.l != r.r) fs.insert(r), sf += r.eval();
}

void ins_gs(int idx, ll v) {
    auto it = gs.lower_bound({ idx, idx + 1, v });
    if (it->a >= v) return;
  
    interval l = { it->l, idx + 1, v };
    interval r = { idx + 1, it->r, it->a };
  
    for (; it->a <= v; gs.erase(it --)) l.l = it->l, sg -= it->eval();
    if (l.l != l.r) gs.insert(l), sg += l.eval();
    if (r.l != r.r) gs.insert(r), sg += r.eval();
}

void solve() {
    fs.clear(), gs.clear();
    fs.insert({ 0, -1, LNF }), fs.insert({ 0, maxn, LNF });
    gs.insert({ 0, -1, LNF }), gs.insert({ 0, maxn, LNF });

    sa = 0, sf = 0, sg = 0;

    int n; cin >> n;
    fs.insert({ 0, n, 0 });
    gs.insert({ 0, n, 0 });
    for (int i = 0; i < n; ++ i) cin >> a[i];

    for (int i = 0; i < n; ++ i) sa += a[i];
    for (int i = 0; i < n; ++ i) ins_fs(i, a[i]);
    for (int i = 0; i < n; ++ i) ins_gs(i, a[i]);

    int q; cin >> q;
    for (int i = 0; i < q; ++ i) {
        int x, v; cin >> x >> v; -- x;

        a[x] += v;
        sa += v;
        ins_fs(x, a[x]);
        ins_gs(x, a[x]);

        cout << (sg + sf - 1ll * n * next(fs.rbegin())->a) - sa << '\n';
    }
}
 
int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t --) solve();
    return 0;
}

---

D. Red Black Tree

D. 概述

給定一顆大小為 $n$ 的樹，每個節點是紅 $(0)$ 或黑 $(1)$，每次操作可以把節點顔色更改。定義紅黑樹性質為對於樹的每個節點，其到所有到葉子節點的路徑上的黑色節點個數相等。問對於每顆子樹把其變成滿足紅黑樹性質所需要的最小操作數。
n ~ 1e5

嘗試枚舉路徑上的黑色節點個數，定義 $f(u, k)$ 為：把以 $u$ 為根的子樹變成滿足紅黑樹性質且路徑上黑色節點個數為 $k$ 所需要的最小操作數，可以得到轉移方程：

$$ \begin{aligned} f(u, k) = \left \{ \begin{aligned} & cost(u,0) + \sum f(v,0) && \text{if}\ \ k=0 \\ & cost(u,1) + \sum f(v,k-1) && \text{if}\ \ k=K \\ & min(cost(u, 0) + \sum f(v,k),\ cost(u,1) + \sum f(v,k-1)) && \text{else}\ \\ \end{aligned} \right. \end{aligned} $$

其中 $v$ 是 $u$ 的兒子，$K$ 是 $k$ 的上界。可以發現 $k$ 的上界是該點到葉子節點的最短路徑，如果不刻意構造數據的話 $k$ 均攤下來應該是 $logn$ 的，所以考慮暴力求解 $f$ 的期望複雜度是 $nlogn$ 的，但如果樹是一條長鏈的話複雜度就會退化到 $n^2$ 。

單獨維護 $k=0$ 的情況，考慮優化 $k>0$ 的情況：
記 $g_u(k) = \sum f(v,k)，\Delta g_u(k)=g_u(k)-g_u(k-1)$，$\Delta cost(u)=cost(u,1)-cost(u,0)$，把上面的方程改寫可得：

$$ f(u,k)=cost(u,0)+g_u(k-1)+min(\Delta g_u(k),\ \Delta cost(u)) $$

這裏需要觀察到如果 $\Delta g_u(k)$ 單調不減，必然存在 $k$ 的分割點使得左邊 $\Delta g_u(k) \lt\Delta cost(u)$，右邊 $\Delta g_u(k) \geq\Delta cost$。即是：

$$ f(u, k) = \left \{ \begin{aligned} & cost(u, 0) + g_u(k) && \text{if k in left}\ \\ & cost(u, 0) + g_u(k-1) + \Delta cost(u) && \text{if k in right}\ \\ \end{aligned} \right. $$

那 $f(u,k)$ 關於 $k$ 的差分數組等效於把 $\Delta cost(u)$ 按序插入到 $\Delta g_u(k)$ 后的某個前綴，它同樣是單調不減的。考慮終止狀態（葉子節點）的 $f$ 的差分數組是單調不減的（差分數組只有一個數），而單調不減的數組的和也是單調不減的（$\Delta g_u(k)$），歸納可得 $\Delta g_u(k)$ 單調不減恆成立。

所以考慮對長鏈優化（只有一個兒子的情況），我們可以對於每個節點都維護一個 $f$ 的差分數組，對於只有一個兒子的節點可以直接繼承兒子的差分數組，然後往差分數組插入一個 $\Delta cost$。這個節點的答案也可以直接繼承兒子的，因爲其所有到葉子節點的路徑的第二個節點必然是這個唯一的兒子。這樣就能確保長鏈的情況下也能有 $nlogn$ 的複雜度，其他情況可以暴力做。

複雜度是 $O(nlogn)$。

也可以在插入 $\Delta cost$ 的時候隨便插入，到有多個兒子的時候再排序，這樣代碼比較好寫，複雜度在 $O(n\log n\log \log n)$。

D. 代碼

#include "bits/stdc++.h"
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
#define INF 0x3f3f3f3f
#define LNF (ll) 0x3f3f3f3f3f3f3f3f 
 
#define maxn 100010
 
int clr[maxn], fz[maxn], res[maxn];
vector<int> G[maxn], F[maxn];
 
int cost(int u, int x) {
    return clr[u] ^ x;
}

int del(int u) {
    return cost(u, 1) - cost(u, 0);
}

void dfs(int u) {
    for (auto& v : G[u]) dfs(v);

    if (G[u].empty()) {
        fz[u] = cost(u, 0), F[u] = { del(u) }, res[u] = 0;
        return;
    }

    if (G[u].size() == 1) {
        int v = G[u][0];
        swap(F[u], F[v]);
        fz[u] = cost(u, 0) + fz[v], F[u].emplace_back(del(u)), res[u] = res[v];
        return;
    }

    int len = INF;
    for (auto& v : G[u]) len = min(len, (int) F[v].size() + 1), sort(F[v].begin(), F[v].end());

    fz[u] = cost(u, 0);
    for (auto& v : G[u]) fz[u] += fz[v];

    F[u].resize(len, 0);
    vector<int> g(len, 0);
    for (auto& v : G[u]) {
        for (int i = 0, cur = fz[v]; i < len; ++ i) {
            g[i] += cur;
            if (i != len - 1) cur += F[v][i];
        }
    }

    res[u] = fz[u];
    for (int i = 1, pf = fz[u], f = fz[u]; i <= len; ++ i, pf = f) {
        f = cost(u, 1) + g[i-1];
        if (i != len) f = min(f, cost(u, 0) + g[i]);

        F[u][i-1] = f - pf;
        res[u] = min(res[u], f);
    }
}

void solve() {
    int n; cin >> n;
  
    string s; cin >> s;
    for (int i = 1; i <= n; ++ i) clr[i] = s[i - 1] - '0';
 
    for (int i = 2; i <= n; ++ i) {
        int p; cin >> p;
        G[p].emplace_back(i);
    }
  
    dfs(1);
 
    for (int i = 1; i <= n; ++ i) cout << (i == 1 ? "" : " ") << res[i];
    cout << '\n';

    for (int i = 0; i <= n; ++ i) G[i].clear(), F[i].clear();
}
 
int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t --) solve();
    return 0;
}

其他

有緣再補