{"problem":{"name":"BZOJ2759 一个动态树好题","description":{"content":"有 $n$ 个未知数 $x_1,x_2,\\dots,x_n$ 和 $n$ 个等式组成的同余方程组：$x_i\\equiv k_i\\times x_{p_i} + b_i \\pmod {10007}$。 你需要进行 $q$ 次操作，每次操作为下列两种情况之一： - `A a`，询问当前 $x_a$ 的解，无解输出 `-1`，多解输出 `-2` 否则输出 $x_a$。 - `C a x y z`，修改","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10660"},"statements":[{"statement_type":"Markdown","content":"有 $n$ 个未知数 $x_1,x_2,\\dots,x_n$ 和 $n$ 个等式组成的同余方程组：$x_i\\equiv k_i\\times x_{p_i} + b_i \\pmod {10007}$。\n\n你需要进行 $q$ 次操作，每次操作为下列两种情况之一：\n- `A a`，询问当前 $x_a$ 的解，无解输出 `-1`，多解输出 `-2` 否则输出 $x_a$。\n- `C a x y z`，修改一个等式 $k_a \\gets x,p_a \\gets y,b_a \\gets z$。\n\n## Input\n\n第一行一个整数 $n$。\n\n接下来 $n$ 行，每行三个整数 $k_i,p_i,b_i$。\n\n接下来一行一个整数 $q$。\n\n再接下来 $q$ 行，每行一个操作，见题意所述。\n\n## Output\n\n对每个询问，输出一行一个整数。\n\n[samples]\n\n## Note\n\n对于所有数据，$k_i,b_i,x_i \\in [0,10007) \\cap \\Z$。$1\\leq n\\leq 3\\times 10^4$，$0\\leq q\\leq 10^5$，其中询问操作占总操作数的约 $80\\%$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10660","tags":["O2优化","动态树 LCT","扩展欧几里德算法"],"sample_group":[["5\n2 2 1\n2 3 2\n2 4 3\n2 5 4\n2 3 5\n5\nA 1\nA 2\nC 5 3 1 1\nA 4\nA 5","4276\n7141\n4256\n2126"]],"created_at":"2026-03-03 11:09:25"}}