F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:祝各位Oier新年快乐,Rp++!
Problem 2759. -- 一个动态树好题

2759: 一个动态树好题

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 952  Solved: 326
[Submit][Status][Discuss]

Description

有N个未知数x[1..n]和N个等式组成的同余方程组:
x[i]=k[i]*x[p[i]]+b[i] mod 10007
其中,k[i],b[i],x[i]∈[0,10007)∩Z
你要应付Q个事务,每个是两种情况之一:
一.询问当前x[a]的解
A a
无解输出-1
x[a]有多解输出-2
否则输出x[a]
二.修改一个等式
C a k[a] p[a] b[a]

Input

N
下面N行,每行三个整数k[i] p[i] b[i]
Q
下面Q行,每行一个事务,格式见题目描述

Output

对每个询问,输出一行一个整数。
对100%的数据,1≤N≤30000,0≤Q≤100000,时限2秒,其中询问事务约占总数的80%

Sample Input

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

Sample Output

4276
7141
4256
2126

HINT

Source

By 范浩强

[Submit][Status][Discuss]

HOME Back