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 
    
     #define ll long longconst 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]
     
      >=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