#P2759. 一个动态树好题

    ID: 1865 传统题 1000ms 512MiB 尝试: 1526 已通过: 312 难度: 8 上传者: 标签>CF2500提高+/省选-根号分块离线查询功能图线性同余方程模逆元逆元线性递推By范浩强

一个动态树好题

题目描述

有 nn 个未知数 x1…nx_{1\dots n} 和 nn 个等式组成的同余方程组:$x_i\equiv k_i\times x_{p_i} +b_i \text{ mod } 10007$ 。

你需要应付 qq 个事务,每个是两种情况之一:

  • A a,询问当前 xax_a 的解,无解输出 -1,多解输出 -2 否则输出 xax_a。
  • C a x y z,修改一个等式,ka←x,pa←y,ba←zk_a\leftarrow x,p_a\leftarrow y,b_a\leftarrow z 。

输入格式

第一行一个整数 nn。 下面 nn 行,每行三个整数 ki,pi,bik_i,p_i,b_i。 接下来一行一个整数 qq。 下面 qq 行,每行一个事务,格式见题目描述。

输出格式

对每个询问,输出一行一个整数。

5
2 2 1
2 3 2
2 4 3
2 5 4
2 3 5
5
A 1
A 2
C 5 3 1 1
A 4
A 5
4276
7141
4256
2126

数据规模与约定

对于 100%100\% 的数据,ki,bi,xi∈[0,10007)∩Zk_i,b_i,x_i\in [0,10007)∩\rm{Z}。 对于 100%100\% 的数据,1≤n≤3×104,0≤q≤1051\le n\le 3\times 10^4,0\le q\le 10^5,其中询问事务约占总数的 80%80\%。