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中.
对于每个询问输出一行表示答案.
说明
对于所有数据，有\(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\).
• \(\text{Subtask1}(3\%),n\le 10,q=0\).
• \(\text{Subtask2}(18\%), n=2\).
• \(\text{Subtask3}(32\%), n,q\le 10^3\).
• \(\text{Subtask4}(33\%), n,q\le 10^5\).
• \(\text{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\n");
else printf("none\n");
}
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\n");
else
{
k>>=1;
printf("%lld\n",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