题解 \(by\;zj\varphi\)
发现每个点的权值都可以表示成 \(\rm k\pm x\)。
那么对于新增的方程，\(\rm x_u+x_v=k\pm x/0\) 且 \(\rm x_u+x_v=s\)。
如果 \(x\) 项系数为 \(0\)，那么就只需判断 \(\rm x_u+x_v=s\) 有无解。
若不为 \(0\)，那么直接解出 \(x_1\) 并判断是否是小数即可。
修改操作就是对一段区间的值加或减，直接树状数组，复杂度 \(\mathcal O\rm((n+q)logn)\)
Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++
struct nanfeng_stream{
template<typename T>inline nanfeng_stream operator>>(T &x) {
ri f=0;x=0;register char ch=gc();
while(!isdigit(ch)) f|=ch=='-',ch=gc();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return x=f?-x:x,*this;
}
}cin;
}
using IO::cin;
namespace nanfeng{
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
typedef long long ll;
static const int N=1e6+7;
int first[N],dep[N],ld[N],rd[N],ww[N],n,q,tot,t=1,opt,u,v;
ll W[N],s;
struct BIT{
#define lowbit(x) ((x)&-(x))
ll c[N];
inline void update(int x,ll k) {for (ri i(x);i<=n;i+=lowbit(i)) c[i]+=k;}
inline ll query(int x) {
ll res(0);
for (ri i(x);i;i-=lowbit(i)) res+=c[i];
return res;
}
}B;
struct edge{int v,w,nxt;}e[N];
inline void add(int u,int v,int w) {e[t].v=v,e[t].w=w,e[t].nxt=first[u],first[u]=t++;}
void dfs(int x,ll w) {
W[ld[x]=p(tot)]=w;
for (ri i(first[x]),v;i;i=e[i].nxt) {
dep[v=e[i].v]=dep[x]+1;
if (dep[v]&1) dfs(v,w-e[i].w);
else dfs(v,w+e[i].w);
}
rd[x]=tot;
}
inline int main() {
//FI=freopen("nanfeng.in","r",stdin);
//FO=freopen("nanfeng.out","w",stdout);
cin >> n >> q;
for (ri i(2),f;i<=n;p(i)) cin >> f >> ww[i],add(f,i,ww[i]);
dfs(1,0);
for (ri i(1),w;i<=tot;p(i)) w=W[i]-W[i-1],B.update(i,w);
for (ri i(1);i<=q;p(i)) {
cin >> opt;
if (opt==2) {
cin >> u >> s;
if (dep[u]&1) B.update(ld[u],-s+ww[u]),B.update(rd[u]+1,s-ww[u]);
else B.update(ld[u],s-ww[u]),B.update(rd[u]+1,-s+ww[u]);
ww[u]=s;
} else {
cin >> u >> v >> s;
ri jd(0);
register ll tmp1=B.query(ld[u]),tmp2=B.query(ld[v]);
if (dep[u]&1) --jd,tmp1*=-1ll;else p(jd);
if (dep[v]&1) --jd,tmp2*=-1ll;else p(jd);
if (!jd) {
if (tmp1+tmp2!=s) puts("none");
else puts("inf");
} else if (jd==2) {
register ll ans=(s-tmp1-tmp2)>>1ll;
if ((ans<<1ll)+tmp1+tmp2==s) printf("%lld\n",ans);
else puts("none");
} else {
register ll ans=(tmp1+tmp2-s)>>1ll;
if ((ans<<1ll)+s==tmp1+tmp2) printf("%lld\n",ans);
else puts("none");
}
}
}
return 0;
}
}
int main() {return nanfeng::main();}