Problem 7 树状数组+转化

$des$
有一棵 $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$.

$sol$
这是一道不错的题，转化后用数据结构维护。
这道题一眼看上去非常不可做
由于对 $x_1$ 进行查询，转化一下，就可以将每个变量都可以表示成 $x_i = k + x_1$ 或者 $x_i = k - x_1$ 的形式，表
示为这个形式之后就可以方便地回答询问了。
对于询问 $u,v,s，$ 只需要将表示 $u$ 和 $v$ 的式子加起来，
这时会出现两种情况：要么会得到 $x_u + x_v = t$ 的形式，此时只需要判断是否有 $s = t$；
要么会得到 $x_u + x_v = t + 2 imes x_1$ 或 $x_u + x_v = t - 2 imes x_1$ ，此时可以解出 $x_1$ ，

注意判断是
否解是整数即可。
对于修改操作，实际上是修改一个子树内的变量的 $k$ ，这里可以将深度为奇数和偶数的点
分开考虑，不难发现就是区间加减。由于只需要单点询问，用一个树状数组维护即可。

#include <bits/stdc++.h>

using namespace std;

#define gc getchar()
inline int read() {
    int x = 0, f = 1; char c = gc;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc;}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x * f;
}

#define LL long long
#define Rep(i, a, b) for(int i = a; i <= b; i ++) 

const int N = 1e6 + 10;

int n, fa[N];
vector <int> V[N];
int W[N], deep[N], lst[N], rst[N], tim;

struct Bit {
    int A[N];
    
    inline int Lowbit(int x) {return x & (-x);}
    
    void Add(int x, int num) {
        for(; x <= n; x += Lowbit(x)) A[x] += num;
    }
    
    inline LL Calc(int x) {
        LL ret = 0;
        for(; x; x -= Lowbit(x)) ret += A[x];
        return ret;
    }
} Tree;

void Dfs(int u, int dep) {
    deep[u] = dep;
    lst[u] = ++ tim;
    int S = V[u].size();
    Rep(i, 0, S - 1) {int v = V[u][i]; Dfs(v, dep ^ 1);}
    rst[u] = tim;
}

int main() {
    n = read(); int q = read();
    Rep(i, 2, n) {
        fa[i] = read(), W[i] = read();
        V[fa[i]].push_back(i);
    }
    
    Dfs(1, 0);
    
    Rep(i, 2, n) if(!deep[i]) W[i] *= -1;
    Rep(i, 2, n) Tree.Add(lst[i], W[i]), Tree.Add(rst[i] + 1, -W[i]);
    
    Rep(qq, 1, q) {
        int opt = read();
        if(opt == 1) {
            int u = read(), v = read(), s = read();
            LL x = Tree.Calc(lst[u]), y = Tree.Calc(lst[v]);
            if(deep[u] && deep[v]) {
                LL ret = x + y - s;
                if(ret % 2 == 0) printf("%lld
", ret >> 1);
                else puts("none");
            } else if(!deep[u] && !deep[v]) {
                LL ret = x + y + s;
                if(ret % 2 == 0) printf("%lld
", ret >> 1);
                else puts("none");
            } else {
                if(!deep[u]) swap(u, v), swap(x, y);
                if(x - y == s) puts("inf");
                else puts("none");
            }
        } else {
            LL x = read(), now = read();
            if(!deep[x]) now = -now;
            Tree.Add(lst[x], now - W[x]), Tree.Add(rst[x] + 1, W[x] - now);
            W[x] = now;
        }
    }
    
    return 0;
}