equation
题目描述
有一棵n 个点的以 1 为根的树, 以及 n 个整数变量xi。树上 i 的父亲是 fi， 每条边i,fi)有一个权值wi，表示一个方程 xi + xfi = wi，这 n-1个方程构成了一个方程组。
现在给出q 个操作，有两种类型:
1 u v s，表示询问加上 xu + xv = s 这个方程后，整个方程组的解的情况。具体来说， 如果方程有唯一解， 输出此时 x1 的值； 如果有无限多个解，输出 inf；如果无解，输出 none. 注意每个询问是独立的。
2 u w，表示将 wu 修改为 w。
solution
首先我们把所有点的权值写成W+x1 或W-x1的样子。
那么每次询问就相当于挑两个点解方程。
现在剩下修改。
修改一个点，它对自己子树的贡献按深度为+1 -1 +1…
一开始先dfs
对于每一个点记一个op为 +1 -1
统计时乘上系数即可。
由于是区间修改，单点查询，可以ccj线段树或差分再树状数组实现
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 1000005
#define ll long long
using namespace std;
int n,q,OP,head[maxn],f[maxn],w[maxn],tot;
int dfst[maxn],dfsn[maxn],sc,op[maxn],val[maxn];
int t1,t2,t3,li,ri,dy[maxn];
struct node{
int v,nex;
}e[maxn];
struct no{
ll v;
}tree[maxn*8];
void ljint t1,int t2){
e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;
}
void dfsint k,int opt){
dfst[k]=++sc;op[k]=opt;dy[sc]=k;
forint i=head[k];i;i=e[i].nex){
val[e[i].v]=-val[k]+w[e[i].v];
dfse[i].v,-opt);
}
dfsn[k]=sc;
}
void buildint k,int L,int R){
ifL==R){
tree[k].v=op[dy[L]]*val[dy[L]];return;
}
int mid=L+R>>1;
buildk*2,L,mid);buildk*2+1,mid+1,R);
}
void chint k,int v,int l,int r){
ifl>=li&&r<=ri){
tree[k].v+=v;
//cout<<"change "<<tree[k].l<<' '<<tree[k].r<<' '<<tree[k].v<<endl;
return;
}
int mid=l+r>>1;
ifli<=mid)chk*2,v,l,mid);
ifri>mid)chk*2+1,v,mid+1,r);
}
ll askint k,int pl,int opt,ll now,int l,int r){
now+=opt*tree[k].v;
ifl==r)return now;
//cout<<tree[k].l<<' '<<tree[k].r<<' '<<now<<endl;
int mid=l+r>>1;
ifpl<=mid)return askk*2,pl,opt,now,l,mid);
else return askk*2+1,pl,opt,now,mid+1,r);
}
int get){
int v=0;char ch;
while!isdigitch=getchar)));v=v+ch-48;
whileisdigitch=getchar)))v=v<<3)+v<<1)+ch-48;
return v;
}
int main)
{
cin>>n>>q;
forint i=2;i<=n;i++){
scanf"%d%d",&f[i],&w[i]);
ljf[i],i);
}
dfs1,1);build1,1,n);
//forint i=1;i<=n;i++)cout<<i<<' '<<val[i]<<' '<<op[i]<<endl;
forint i=1;i<=q;i++){
scanf"%d",&OP);
ifOP==1){
scanf"%d%d%d",&t1,&t2,&t3);
ll v1=ask1,dfst[t1],op[t1],0,1,n),v2=ask1,dfst[t2],op[t2],0,1,n);
ifop[t1]+op[t2]==0){
ifv1+v2==t3)puts"inf");
else puts"none");
}
else {
ll tmp=t3-v1-v2;
iftmp%2==0)printf"%lld
",tmp/2*op[t1]);
else puts"none");
}
}
else {
scanf"%d%d",&t1,&t2);
li=dfst[t1],ri=dfsn[t1];
ch1,-op[t1]*w[t1],1,n);w[t1]=t2;
ch1,op[t1]*w[t1],1,n);
}
}
return 0;
}