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 \times x_1$ 或 $x_u + x_v = t - 2 \times x_1$ ，此时可以解出 $x_1$ ，

注意判断是

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

#include <bits/stdc++.h>

using namespace std;

#define gc getchar()

inline int read() {

    int x = , f = ; char c = gc;

    while(c < '' || c > '') {if(c == '-') f = -; c = gc;}

    while(c >= '' && c <= '') x = x *  + c - '', 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 + ;

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 = ;

        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, , S - ) {int v = V[u][i]; Dfs(v, dep ^ );}

    rst[u] = tim;

}

int main() {

    n = read(); int q = read();

    Rep(i, , n) {

        fa[i] = read(), W[i] = read();

        V[fa[i]].push_back(i);

    }

    Dfs(, );

    Rep(i, , n) if(!deep[i]) W[i] *= -;

    Rep(i, , n) Tree.Add(lst[i], W[i]), Tree.Add(rst[i] + , -W[i]);

    Rep(qq, , q) {

        int opt = read();

        if(opt == ) {

            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 %  == ) printf("%lld\n", ret >> );

                else puts("none");

            } else if(!deep[u] && !deep[v]) {

                LL ret = x + y + s;

                if(ret %  == ) printf("%lld\n", ret >> );

                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] + , W[x] - now);

            W[x] = now;

        }

    }

    return ;

}

巴特西

Problem 7 树状数组+转化

最新文章

热门文章