Equation

equation.cpp/in/out

• 时间限制：1.5s
• 空间限制：512MB

题目描述

有一棵 $n$ 个点的以 1 为根的树，以及 $n$ 个整数变量 $x_i$。树上 $i$ 的父亲是 $f_i$，每条边 $(i, f_i)$ 有一个权值 $w_i$，表示一个方程 $x_i + x_{f_i} = w_i$，这 $n-1$ 个方程构成了一个方程组。

现在给出 $q$ 个操作，有两种类型：

• 1 u v s，表示询问加上 $x_u + x_v = s$ 这个方程后，整个方程组的解的情况。具体来说，如果方程有唯一解，输出此时 $x_1$ 的值；如果有无限多个解，输出 inf；如果无解，输出 none。注意每个询问是独立的。
• 2 u w，表示将 $w_u$ 修改为 $w$。

输入格式

从文件 equation.in 中读入数据。

第一行两个整数 $n, q$。

接下来 $n-1$ 行，第 $i$ 行有两个整数 $f_{i+1}$ 和 $w_{i+1}$。

接下来 $q$ 行，每行表示一个操作，格式见问题描述。

输出格式

输出到文件 equation.out 中。

对于每个询问输出一行表示答案。

样例输入

2 7
1 4
1 1 2 5
1 1 2 4
1 1 1 3
1 2 2 6
2 2 3
1 2 2 10
1 2 2 -10

样例输出

none
inf
none
1
-2
8

数据范围

对于所有数据，有 $1 \le n, q \le 10^6$，$1 \le f_i \le i-1$，$1 \le u, v \le n$，$-10^3 \le w, w_i \le 10^3$，$-10^9 \le s \le 10^9$。

• Subtask 1 (3%)：$n \le 10$，$q = 0$。
• Subtask 2 (18%)：$n = 2$。
• Subtask 3 (32%)：$n, q \le 10^3$。
• Subtask 4 (33%)：$n, q \le 10^5$。
• Subtask 5 (14%)：没有特殊的约束。