{"problem":{"name":"「KDOI-06-S」树上异或","description":{"content":"给定一棵包含 $n$ 个节点的树，第 $i$ 个点有一个点权 $x_i$。 对于树上的 $n-1$ 条边，每条边选择删除或不删除，有 $2^{n-1}$ 种选择是否删除每条边的方案。 对于每种删除边的方案，设删除后的图包含 $k$ 个连通块，定义这个方案的权值为图中连通块点权异或和的乘积。形式化地说，若这张图包含连通块 $C_1,C_2,\\ldots,C_k$，其中 $C_i$ 是第 $i$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9745"},"statements":[{"statement_type":"Markdown","content":"给定一棵包含 $n$ 个节点的树，第 $i$ 个点有一个点权 $x_i$。\n\n对于树上的 $n-1$ 条边，每条边选择删除或不删除，有 $2^{n-1}$ 种选择是否删除每条边的方案。\n\n对于每种删除边的方案，设删除后的图包含 $k$ 个连通块，定义这个方案的权值为图中连通块点权异或和的乘积。形式化地说，若这张图包含连通块 $C_1,C_2,\\ldots,C_k$，其中 $C_i$ 是第 $i$ 个连通块的顶点集合，设 $v_i=\\bigoplus_{u\\in C_i} x_u$，则这个方案的权值为 $v_1\\times v_2\\times \\cdots\\times v_k$。\n\n求这 $2^{n-1}$ 种删除边的方案的**权值**之和，答案对 $998~244~353$ 取模。\n\n## Input\n\n从标准输入读入数据。\n\n输入的第一行包含一个正整数 $n$，表示树的节点个数。\n\n第二行 $n$ 个非负整数 $x_1,x_2,\\ldots,x_n$，表示每个点的点权。\n\n第三行 $n-1$ 个正整数 $f_2,f_3,\\ldots,f_n$，表示节点 $i$ 与 $f_{i}$ 之间有一条无向边。\n\n## Output\n\n输出到标准输出。\n\n输出包含一行一个整数，表示所有 $2^{n-1}$ 种删除边的方案的**权值**之和，答案对 $998~244~353$ 取模。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n有四种删除边的方案：\n\n* 不删除边：图有且仅有一个连通块，权值为 $1\\oplus2\\oplus3=0$。\n* 删除 $(1,2)$ 一条边：图包含两个连通块，权值为 $(1\\oplus3)\\times2=4$。\n* 删除 $(1,3)$ 一条边：图包含两个连通块，权值为 $(1\\oplus2)\\times3=9$。\n* 删除 $(1,2)$，$(1,3)$ 两条边：图包含三个连通块，权值为 $1\\times2\\times3=6$。\n\n所有方案权值的总和为 $0+4+9+6=19$。\n\n**【样例 #3】**\n\n见选手目录下的 `xor/xor3.in` 与 `xor/xor3.ans`。\n\n这个样例满足测试点 $6\\sim7$ 的条件限制。\n\n**【样例 #4】**\n\n见选手目录下的 `xor/xor4.in` 与 `xor/xor4.ans`。\n\n这个样例满足测试点 $8$ 的条件限制。\n\n**【样例 #5】**\n\n见选手目录下的 `xor/xor5.in` 与 `xor/xor5.ans`。\n\n这个样例满足测试点 $9$ 的条件限制。\n\n**【样例 #6】**\n\n见选手目录下的 `xor/xor6.in` 与 `xor/xor6.ans`。\n\n这个样例满足测试点 $19\\sim21$ 的条件限制。\n\n***\n\n**【数据范围】**\n\n对于所有数据保证：$1\\leq n\\leq5\\times10^5$，$0\\leq x_i\\leq10^{18}$，$1\\leq f_i<i$。\n\n| 测试点编号 | $n\\leq$ | $x_i$ | 特殊性质 |\n|:--:|:--:|:--:|:--:|\n| $1\\sim2$ | $12$ | $\\leq10^9$ | 无 |\n| $3$ | $2000$ | $=1$ | 无 |\n| $4$ | $10^5$ | $=1$ | A |\n| $5$ | $10^5$ | $=1$ | B |\n| $6\\sim7$ | $10^5$ | $=1$ | 无 |\n| $8$ | $10^5$ | $\\leq7$ | A |\n| $9$ | $10^5$ | $\\leq7$ | B |\n| $10\\sim11$ | $10^5$ | $\\leq7$ | 无 |\n| $12\\sim16$ | $200$ | $\\leq8191$ | 无 |\n| $17$ | $10^5$ | $\\leq10^9$ | A |\n| $18$ | $10^5$ | $\\leq10^9$ | B |\n| $19\\sim21$ | $10^5$ | $\\leq10^9$ | 无 |\n| $22\\sim25$ | $5\\times10^5$ | $\\leq10^{18}$ | 无 |\n\n* 特殊性质 A：保证对于任意 $1< i\\le n$，$f_i=i-1$。\n* 特殊性质 B：保证对于任意 $1< i\\le n$，$f_i=1$。\n\n***\n\n**【提示】**\n\n$\\oplus$ 表示按位异或运算。\n\n本题输入输出量较大，请使用适当的 I/O 方式。\n\n**请注意常数因子对程序运行效率产生的影响。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9745","tags":["动态规划 DP","2023","洛谷原创","O2优化","树形 DP","位运算","洛谷月赛"],"sample_group":[["3\n1 2 3\n1 1","19"],["5\n3 4 5 6 7\n1 1 2 2","5985"]],"created_at":"2026-03-03 11:09:25"}}