2018.11.07-dtoj-4032-equation

题目描述:

有一棵 $n$ 个点的以 $1$ 为根的树, 以及 $n$ 个整数变量 $x_i$ 。树上 $i$ 的父亲是 $f_i$ , 每条边 $(i,f_i)$ 有一个权值 $w_i$ ,表示一个方程 $x_i + xf_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$ 。

输入:

第一行两个整数 $n,q$ 。

接下来 $n-1$ 行,第 $i$ 行有两个整数 $f_i+1$ 和 $w_i+1$ 。

接下来 $q$ 行,每行表示一个操作,格式见问题描述。

输出:

对于每个询问输出一行表示答案。

数据范围:

 对于所有数据 , 有 1n,q106,1fii1,1u,vn,103w,wi103,109s109 

算法标签:树状数组

思路:

 倘若把每个点都用常数和 $x_1$ 表示,我们可以发现偶数层的数呈现 $x_i=k-x_1$ ,奇数层是 $x_i=k+x_1$ 。于是倘若没有修改我们容易得出答案。但是考场我维护修改只想到树剖,然后就代码+++++,然后就心态崩了,弃了。结束之后,发现可以用树状数组差分维护,(小本本记下!!好思想!)因为每个值的修改只会影响到自己的子树,所以考虑在 $dfn[x]$ 的地方 $+v$ , $dfn[x]+sz[x]$ 的地方 $-v$ ,前缀和即为构成的贡献。妙啊!!我好菜...临退役...

以下代码:

#include<bits/stdc++.h>
#define il inline
#define LL long long
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N=1e6+5;
int n,q,head[N],to[N],ne[N],w[N],dfn[N],cnt,tot,d[N],sz[N],t[2][N],v[N];
il int read(){int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;}
il void insert(int x,int y){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}
il void ins(int op,int x,int v){for(x;x<=n;x+=x&-x)t[op][x]+=v;}
il int query(int op,int x){int res=0;for(x;x;x-=x&-x)res+=t[op][x];return res;}
il void dfs(int x){
    dfn[x]=++tot;sz[x]=1;
    for(int i=head[x];i;i=ne[i]){
        d[to[i]]=d[x]+1;v[to[i]]=w[to[i]]-v[x];
        dfs(to[i]);sz[x]+=sz[to[i]];
    }
}
int main()
{
    n=read();q=read();
    for(int i=2;i<=n;i++){
        int x=read(),z=read();insert(x,i);w[i]=z;
    }
    d[1]=1;dfs(1);
    while(q--){
        int op=read();
        if(op==1){
            int x=read(),y=read(),s=read();
            int res1,res2;
            res1=query(d[x]&1,dfn[x])+v[x];
            res2=query(d[y]&1,dfn[y])+v[y];
            if(((d[x]&1)^(d[y]&1))==0){
                LL kk=(LL)res1+(LL)res2;
                if(d[x]&1){
                    kk=(LL)s-kk;
                    if(kk&1ll)puts("none");else printf("%d
",(kk>>1ll));
                }
                else{
                    kk=kk-(LL)s;
                    if(kk&1ll)puts("none");else printf("%d
",(kk>>1ll));
                }
            }
            else{
                if(res1+res2==s)puts("inf");
                else puts("none");
            }
        }
        else{
            int x=read(),z=read();int c=z-w[x];
            w[x]=z;ins(d[x]&1,dfn[x],c);ins(d[x]&1,dfn[x]+sz[x],-c);
            ins((d[x]&1)^1,dfn[x],-c);ins((d[x]&1)^1,dfn[x]+sz[x],+c);
        }
    }
  return 0;
}
View Code
原文地址:https://www.cnblogs.com/Jessie-/p/9925178.html