{"problem":{"name":"[SNOI2024] 字符树","description":{"content":"给你一个 $n$ 个点的有根树，根为 $1$。每条边上有一个字符 $c = \\{0, 1\\}$。$S_u$ 表示从根到 $u$ 的路径上每条边的字符依次写下来组成的字符串。保证每个节点向儿子的边上的字符互不相同。 对每个点 $u$，有一个价值 $\\mathit{val}_u$ 和一个限制 $a_u$。对每个点 $u$，如果点 $v$ 满足 $S_u$ 是 $S_v$ 的后缀。那么我们认为 $v$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":7000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10065"},"statements":[{"statement_type":"Markdown","content":"给你一个 $n$ 个点的有根树，根为 $1$。每条边上有一个字符 $c = \\{0, 1\\}$。$S_u$ 表示从根到 $u$ 的路径上每条边的字符依次写下来组成的字符串。保证每个节点向儿子的边上的字符互不相同。\n\n对每个点 $u$，有一个价值 $\\mathit{val}_u$ 和一个限制 $a_u$。对每个点 $u$，如果点 $v$ 满足 $S_u$ 是 $S_v$ 的后缀。那么我们认为 $v$ 是的 $u$ 扩展点。\n\nAlice 手里有一个字符串 $S$，初始令 $S = S_u$，现在他可以删掉若干末尾的字符，使得 $S$ 变成 $S'$。并将 $S'$ 告诉给 Bob。\n\nBob 获得了一个字符串 $S'$，他需要在 $S'$ 之后加入若干字符，并获得 $S''$。对于某个 $u$ 的扩展点 $v$，满足 $S'' = S_v$，并且 $\\lvert S' \\rvert \\ge a_v$，那么 Bob 就获得了 $\\mathit{val}_v$ 的收益，当然 Bob 只能进行一次这样的操作，所以他会选择符合条件的 $v$ 里，$\\mathit{val}_v$ 最大的那个。如果没有符合条件的 $v$，Bob 只能获得 $0$ 的收益。\n\n现在 Alice 想知道，对于删除 $0 \\sim \\lvert S \\rvert$ 个字符，总计 $\\lvert S \\rvert + 1$ 种删除方式里 Bob 能获得权值之和是多少？\n\n对于每个 $u$，你都需要回答 Alice 的询问。\n\n形式化地说：\n\n我们需要对每个点 $u$ 求出 $\\mathit{ans}_u = \\sum\\limits_{0 \\le i \\le \\lvert S_u \\rvert} \\max\\limits_{i \\ge a_v \\land S_u = S_v[\\lvert S_v \\rvert - \\lvert S_u \\rvert + 1, \\lvert S_v \\rvert] \\land S_u[1, i] = S_v[1, i]} \\mathit{val}_v$。\n\n特殊的，如果对于某个 $u$，不存在任何 $v$ 满足条件，那么 $\\max = 0$。\n\n其中 $S[l, r]$ 表示字符串 $S$ 的第 $l$ 到第 $r$ 个字符组成的字符串。特殊的，$S[x + 1, x]$ 表示空串。$\\lvert S \\rvert$ 表示字符串 $S$ 的长度，$\\land$ 表示且。\n\n## Input\n\n多组测试数据，第一行一个整数 $T$ 表示数据组数。  \n对于每组测试数据，第一行一个正整数 $n$，表示节点个数。  \n接下来 $n - 1$ 行，每行两个整数 $\\mathit{fa}_i, c_i$ 表示第 $i$ 个点的父亲编号，以及边上的字符。  \n接下来一行 $n$ 个正整数 $\\mathit{val}_1, \\mathit{val}_2, \\ldots, \\mathit{val}_n$。  \n接下来一行 $n$ 个非负整数 $a_1, a_2, \\ldots, a_n$。\n\n## Output\n\n输出一行 $n$ 个整数 $\\mathit{ans}_1, \\mathit{ans}_2, \\ldots, \\mathit{ans}_n$。\n\n[samples]\n\n## Note\n\n**【样例 \\#1 解释】**\n\n以下表格表示当 $u, i$ 固定时，式子中 $\\mathit{val}_v$ 的最大值。\n\n| | $u = 1$ | $u = 2$ | $u = 3$ | $u = 4$ | $u = 5$ |\n|:-:|:-:|:-:|:-:|:-:|:-:|\n| $i = 0$ | $3$ | $0$ | $3$ | $0$ | $0$ |\n| $i = 1$ | - | $4$ | $3$ | $4$ | $0$ |\n| $i = 2$ | - | - | - | $4$ | $5$ |\n\n---\n\n**【样例 \\#2】**\n\n见附件中 `tree/tree2.in` 与 `tree/tree2.ans`。\n\n这个样例满足测试点 $3 \\sim 5$ 的条件限制。\n\n---\n\n**【样例 \\#3】**\n\n见附件中 `tree/tree3.in` 与 `tree/tree3.ans`。\n\n这个样例满足测试点 $9 \\sim 10$ 的条件限制。\n\n---\n\n**【样例 \\#4】**\n\n见附件中 `tree/tree4.in` 与 `tree/tree4.ans`。\n\n这个样例满足测试点 $11 \\sim 12$ 的条件限制。\n\n---\n\n**【数据范围】**\n\n对于所有数据保证 $1 \\le T \\le 5$，$1 \\le n \\le 5 \\times {10}^5$，$1 \\le \\mathit{val}_i \\le {10}^9$，$1 \\le \\mathit{fa}_i < i$，$c_i = \\{0, 1\\}$，$0 \\le a_i \\le n$。\n\n具体如下：\n\n| 测试点编号 | $n \\le$ | 特殊性质 |\n|:-:|:-:|:-:|\n| $1 \\sim 2$ | $100$ | 无 |\n| $3 \\sim 5$ | $2 \\times {10}^3$ | 无 |\n| $6 \\sim 8$ | ${10}^4$ | 无 |\n| $9 \\sim 10$ | ${10}^5$ | A |\n| $11 \\sim 12$ | ${10}^5$ | B |\n| $13 \\sim 16$ | ${10}^5$ | 无 |\n| $17 \\sim 20$ | $5 \\times {10}^5$ | 无 |\n\n特殊性质 A：$c_i = 0$。  \n特殊性质 B：$\\mathit{fa}_i = \\lfloor \\frac{i}{2} \\rfloor$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10065","tags":["各省省选","2024","O2优化","陕西"],"sample_group":[["1\n5\n1 0\n1 1\n2 0\n2 1\n1 2 3 4 5\n0 1 0 1 2\n","3 4 6 8 5\n"]],"created_at":"2026-03-03 11:09:25"}}