Equation
题目描述
有一棵(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中.
对于每个询问输出一行表示答案.
说明
对于所有数据，有(1le n,qle 10^6,1le f_ile i -1,1le u,vle n; -10^3le w,w_ile 10^3,-10^9le sle 10^9).
• ( ext{Subtask1}(3\%),nle 10,q=0).
• ( ext{Subtask2}(18\%), n=2).
• ( ext{Subtask3}(32\%), n,qle 10^3).
• ( ext{Subtask4}(33\%), n,qle 10^5).
• ( ext{Subtask5}(14\%)),没有特殊的约束.
给个1e5,给个1e6真的坑。
1e6就认为是(O(n))做法好吗（反正我大常数这辈子过不了1e6的(nlogn)了
不过为了卡两个(log)的还可以理解了
发现连上一条边后，把路径的边权正负相加可以消去很多项。
当路径长度为奇数，判断无解or多解
偶数，解出来判断是否有整数解
然后求上去就行了
发现我们要维护路径求和和单点修改
可以无脑树剖但是不能拿满分
路径求和可以根据lca分成两个分别求
维护一个到根节点的路径长度
跑一下dfs序，就变成了维护区间求和和单点加，树状数组就可以了
然而我常数真的大。。
细节处理起来听麻烦的
Code:
#include <cstdio>
#define ll long long
const int N=1e6+10;
int read()
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9') {if(c=='-') f=-f;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
int n,q;
int head[N],to[N],Next[N],cnt;
void add(int u,int v)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int dep[N],f[N][21],w[N],dfn[N],siz[N],dfsclock,tmp;
ll s[N];
void swap(int &x,int &y){tmp=x,x=y,y=tmp;}
void modify(int x,ll de)
{
for(int i=x;i<=n;i+=i&-i)
s[i]+=de;
}
ll query(int x)
{
ll sum=0;
for(int i=x;i;i-=i&-i)
sum+=s[i];
return sum;
}
void dfs(int now)
{
dfn[now]=++dfsclock,siz[now]=1;
modify(dfn[now],w[now]*(dep[now]&1?1:-1));
for(int i=1;f[now][i-1];i++) f[now][i]=f[f[now][i-1]][i-1];
for(int i=head[now];i;i=Next[i])
dep[to[i]]=dep[now]+1,dfs(to[i]),siz[now]+=siz[to[i]];
modify(dfn[now]+siz[now],w[now]*(dep[now]&1?-1:1));
}
int LCA(int u,int v)
{
for(int i=20;~i;i--)
if(dep[f[u][i]]>=dep[v])
u=f[u][i];
if(u==v) return u;
for(int i=20;~i;i--)
if(f[u][i]!=f[v][i])
u=f[u][i],v=f[v][i];
return f[u][0];
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
n=read(),q=read();
for(int i=2;i<=n;i++)
f[i][0]=read(),w[i]=read(),add(f[i][0],i);
dfs(1);
for(int p,op,u,v,s,i=1;i<=q;i++)
{
op=read();
if(op==1)
{
u=read(),v=read(),s=read();
if(dep[u]<dep[v]) swap(u,v);
int lca=LCA(u,v);p=u;
if(dep[u]-dep[v]&1)
{
ll k=(query(dfn[u])-query(dfn[lca]))*(dep[u]&1?1:-1);
k+=(query(dfn[v])-query(dfn[lca]))*(dep[v]&1?1:-1);
if(s==k) printf("inf
");
else printf("none
");
}
else
{
ll k=1ll*(query(dfn[u])-query(dfn[lca]))*(dep[u]&1?1:-1);
k+=1ll*(query(dfn[v])-query(dfn[lca]))*(dep[v]&1?-1:1);
k=k+s;
if(k&1) printf("none
");
else
{
k>>=1;
printf("%lld
",query(dfn[p])-k*(dep[p]&1?1:-1));
}
}
}
else
{
u=read();
p=read();
modify(dfn[u],(p-w[u])*(dep[u]&1?1:-1));
modify(dfn[u]+siz[u],(w[u]-p)*(dep[u]&1?1:-1));
w[u]=p;
}
}
return 0;
}
2018.10.6