题目描述：
有一棵 $n$ 个点的以 $1$ 为根的树, 以及 $n$ 个整数变量 $x_i$ 。树上 $i$ 的父亲是 $f_i$ ， 每条边 $(i,f_i)$ 有一个权值 $w_i$ ，表示一个方程 $x_i + xf_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$ 。
输入：
第一行两个整数 $n,q$ 。
接下来 $n-1$ 行，第 $i$ 行有两个整数 $f_i+1$ 和 $w_i+1$ 。
接下来 $q$ 行，每行表示一个操作，格式见问题描述。
输出：
对于每个询问输出一行表示答案。
数据范围：
对于所有数据 ， 有 1≤n,q≤106,1≤fi≤i−1,1≤u,v≤n,−103≤w,wi≤103,−109≤s≤109
算法标签：树状数组
思路：
倘若把每个点都用常数和 $x_1$ 表示，我们可以发现偶数层的数呈现 $x_i=k-x_1$ ,奇数层是 $x_i=k+x_1$ 。于是倘若没有修改我们容易得出答案。但是考场我维护修改只想到树剖，然后就代码+++++，然后就心态崩了，弃了。结束之后，发现可以用树状数组差分维护，（小本本记下！！好思想！）因为每个值的修改只会影响到自己的子树，所以考虑在 $dfn[x]$ 的地方 $+v$ ， $dfn[x]+sz[x]$ 的地方 $-v$ ,前缀和即为构成的贡献。妙啊！！我好菜...临退役...
以下代码：
#include#define il inline#define LL long long#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=1e6+5;int n,q,head[N],to[N],ne[N],w[N],dfn[N],cnt,tot,d[N],sz[N],t[2][N],v[N];il int read(){ int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;}il void insert(int x,int y){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}il void ins(int op,int x,int v){ for(x;x<=n;x+=x&-x)t[op][x]+=v;}il int query(int op,int x){ int res=0;for(x;x;x-=x&-x)res+=t[op][x];return res;}il void dfs(int x){ dfn[x]=++tot;sz[x]=1; for(int i=head[x];i;i=ne[i]){ d[to[i]]=d[x]+1;v[to[i]]=w[to[i]]-v[x]; dfs(to[i]);sz[x]+=sz[to[i]]; }}int main(){ n=read();q=read(); for(int i=2;i<=n;i++){ int x=read(),z=read();insert(x,i);w[i]=z; } d[1]=1;dfs(1); while(q--){ int op=read(); if(op==1){ int x=read(),y=read(),s=read(); int res1,res2; res1=query(d[x]&1,dfn[x])+v[x]; res2=query(d[y]&1,dfn[y])+v[y]; if(((d[x]&1)^(d[y]&1))==0){ LL kk=(LL)res1+(LL)res2; if(d[x]&1){ kk=(LL)s-kk; if(kk&1ll)puts("none");else printf("%d\n",(kk>>1ll)); } else{ kk=kk-(LL)s; if(kk&1ll)puts("none");else printf("%d\n",(kk>>1ll)); } } else{ if(res1+res2==s)puts("inf"); else puts("none"); } } else{ int x=read(),z=read();int c=z-w[x]; w[x]=z;ins(d[x]&1,dfn[x],c);ins(d[x]&1,dfn[x]+sz[x],-c); ins((d[x]&1)^1,dfn[x],-c);ins((d[x]&1)^1,dfn[x]+sz[x],+c); } } return 0;}