题解

先把树放到一边。一次查询给出的路径，按顺序写出来就是一段只含 $+1,-1$ 的序列。我们要问其中有没有连续子段的和为 $k$，并且允许空段。

如果点权可以是任意整数，仅知道最大、最小子段和肯定不够。但这里每个数都恰好是 $+1$ 或 $-1$，可取到的子段和之间不会留下空缺。

设最大子段和为 $R$。取一段和为 $R$ 的子段，从它的左端开始逐个加入元素，部分和由 $0$ 走到 $R$，每一步只加一或减一，因此中间一定经过 $0,1,\ldots,R$。这些部分和对应的前缀也都是原路径上的连续子段。

对最小子段和 $L$ 做同样的分析，就能取到 $L,L+1,\ldots,0$。空段又保证了 $0$ 合法，所以查询等价于

$$L\le k\le R.$$

接下来只需要维护路径的最大、最小子段和。

两段路径接起来，需要哪些信息

考虑先经过片段 $A$，再经过片段 $B$。最大子段可能完全在 $A$，完全在 $B$，或者跨过两段的连接处。

跨过连接处时，它一定是 $A$ 的一个后缀，加上 $B$ 的一个前缀。因此只保存整段的最大子段和不够，还要保存最大前缀和、最大后缀和。

为了继续合并前缀、后缀，还需要整段总和。于是记 $sum$ 为总和，$pre,suf,sub$ 分别为最大前缀、后缀、子段和，有

$$\begin{aligned} sum_{AB}&=sum_A+sum_B,\\ pre_{AB}&=\max(pre_A,sum_A+pre_B),\\ suf_{AB}&=\max(suf_B,sum_B+suf_A),\\ sub_{AB}&=\max(sub_A,sub_B,suf_A+pre_B). \end{aligned}$$

前缀要么停在 $A$ 里，要么走完 $A$ 再取 $B$ 的前缀；后缀同理。子段的三种情况也已经列全，所以这些量可以准确合并。

最小值再存一套 $minpre,minsuf,minsub$，公式里的 max 全部换成 min 即可。总共七个量，总和只存一份。

这些前缀、后缀、子段都允许为空。空片段的七个量全为 $0$；单点 $x$ 的总和为 $x$，三个最大值为 $\max(0,x)$，三个最小值为 $\min(0,x)$。

先解决链，再把树路径拆成链

如果树本来就是一条链，就按链上的顺序编号，用线段树维护这七个量。翻转一个点，修改对应叶子，再向上合并。路径查询就是一次区间查询。

一般树上使用树链剖分，把一条路径拆成若干条重链上的连续区间。每个区间在线段树里查询，然后按实际经过顺序接起来。

这里最容易写错的是方向。

线段树中的一条重链按从上到下编号，但从 $u$ 走向它的祖先，是从下到上走。整段倒过来以后，总和和最大、最小子段和都不变，前缀与后缀则交换。因此写一个反转信息的函数，只交换 $pre,suf$，以及 $minpre,minsuf$。

查询时维护两段已处理的信息 $left,right$，让完整路径始终是

$$left+\text{尚未处理的中间路径}+right.$$

两端还不在同一条重链时，处理链头更深的一端。

• 处理 $u$ 侧，查出从链头到 $u$ 的区间，反转后接到 $left$ 后面，再让 $u$ 跳到链头父亲。
• 处理 $v$ 侧，查出从链头到 $v$ 的区间，不反转，放到 $right$ 前面，再让 $v$ 跳到链头父亲。

$v$ 侧的新片段要放在前面，是因为它在实际路径上，比之前取出的靠近 $v$ 的那些片段更早经过。

两端最终在同一条重链上，查出它们之间的区间，并调整成从当前 $u$ 到当前 $v$ 的方向。把这段接到 $left$ 后面，再合并 $left+right$，得到整条路径的七个量。读出 $minsub,maxsub$，判断 $k$ 是否在它们之间。

每次取出的都是剩余路径的一端，取完后跳到链头父亲，片段之间没有重复点。最后同链部分把中间剩余的点一次取完，所以最近公共祖先也只计算一次。

整条路径反转不会改变答案，但这不代表合并时能随便交换几段。局部顺序变了，会产生原路径中并不存在的连续子段。

复杂度与边界

每跨过一条轻边向上，子树大小至少翻倍，所以一条路径只会拆成 $O(\log n)$ 段。每段线段树查询为 $O(\log n)$，单次查询 $O(\log^2 n)$；单点修改 $O(\log n)$。总时间 $O(n+q\log^2 n)$，空间 $O(n)$。

$k=0$ 时空段总能满足；$u=v$ 时按一个点的区间正常查询。和的绝对值不超过 $n$，int 足够。参考程序用显式遍历处理原树，避免长链上的递归 DFS 栈过深；线段树递归只有对数层。

部分分怎么做

$n,q\le3000$ 的 15 分，可以每次把路径上的点取出来，线性扫描求最大、最小子段和。扫描时分别维护以当前点结尾、允许空段的最大值和最小值，更新为

$$hi=\max(0,hi+x),\qquad lo=\min(0,lo+x).$$

沿途再取 $hi$ 的最大值、$lo$ 的最小值即可。修改直接改点权，总时间 $O(n+nq)$、空间 $O(n)$。

没有修改的 20 分可以用倍增存路径信息。令 $F[j][v]$ 表示从 $v$ 开始向上连续 $2^j$ 个点的七个量，不包含跳完这些点后到达的祖先。合并两段长为 $2^{j-1}$ 的信息，就得到长为 $2^j$ 的信息。

查询时两端分别向上跳，把经过的片段按向上顺序积累，到最近公共祖先 $w$ 后，拼成 $u$ 侧、单点 $w$、反转后的 $v$ 侧。这个不包含跳转终点的约定能避免重复统计 $w$。预处理时间和空间 $O(n\log n)$，每次查询 $O(\log n)$。出现修改后，许多预处理片段会一起失效，因此这档专门保证没有修改。

链的 20 分使用前面介绍的线段树即可，时间 $O(n+q\log n)$、空间 $O(n)$。需要沿实际的链重新编号，不能默认输入编号就是链上顺序。

把规模做法、静态倍增和链上线段树按条件组合，可以保证前三档的 55 分。

参考代码

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

struct Info {
    int sum = 0, maxpre = 0, maxsuf = 0, maxsub = 0;
    int minpre = 0, minsuf = 0, minsub = 0;
};
Info merge_info(const Info &a, const Info &b) {
    Info c;
    c.sum = a.sum + b.sum;
    c.maxpre = max(a.maxpre, a.sum + b.maxpre);
    c.maxsuf = max(b.maxsuf, b.sum + a.maxsuf);
    c.maxsub = max({a.maxsub, b.maxsub, a.maxsuf + b.maxpre});
    c.minpre = min(a.minpre, a.sum + b.minpre);
    c.minsuf = min(b.minsuf, b.sum + a.minsuf);
    c.minsub = min({a.minsub, b.minsub, a.minsuf + b.minpre});
    return c;
}
Info reverse_info(Info a) {
    swap(a.maxpre, a.maxsuf);
    swap(a.minpre, a.minsuf);
    return a;
}
Info one(int x) {
    Info z;
    z.sum = x;
    z.maxpre = z.maxsuf = z.maxsub = max(0, x);
    z.minpre = z.minsuf = z.minsub = min(0, x);
    return z;
}
struct SegTree {
    int n;
    vector<Info> t;
    SegTree(const vector<int> &a) : n((int)a.size() - 1), t(4 * n + 4) { build(1, 1, n, a); }
    void build(int p, int l, int r, const vector<int> &a) {
        if (l == r) { t[p] = one(a[l]); return; }
        int m = (l + r) / 2;
        build(p * 2, l, m, a);
        build(p * 2 + 1, m + 1, r, a);
        t[p] = merge_info(t[p * 2], t[p * 2 + 1]);
    }
    void set(int p, int l, int r, int at, int x) {
        if (l == r) { t[p] = one(x); return; }
        int m = (l + r) / 2;
        if (at <= m) set(p * 2, l, m, at, x);
        else set(p * 2 + 1, m + 1, r, at, x);
        t[p] = merge_info(t[p * 2], t[p * 2 + 1]);
    }
    Info get(int p, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return t[p];
        int m = (l + r) / 2;
        if (qr <= m) return get(p * 2, l, m, ql, qr);
        if (ql > m) return get(p * 2 + 1, m + 1, r, ql, qr);
        return merge_info(get(p * 2, l, m, ql, qr), get(p * 2 + 1, m + 1, r, ql, qr));
    }
    void set(int at, int x) { set(1, 1, n, at, x); }
    Info get(int l, int r) const { return get(1, 1, n, l, r); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<vector<int>> g(n + 1);
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> parent(n + 1), depth(n + 1), size(n + 1, 1), heavy(n + 1), order;
    size[0] = 0;
    order.reserve(n);
    order.push_back(1);
    for (int k = 0; k < (int)order.size(); ++k) {
        int u = order[k];
        for (int v : g[u]) if (v != parent[u]) {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            order.push_back(v);
        }
    }
    for (int k = n - 1; k >= 0; --k) {
        int u = order[k];
        for (int v : g[u]) if (v != parent[u]) {
            size[u] += size[v];
            if (size[v] > size[heavy[u]]) heavy[u] = v;
        }
    }
    vector<int> head(n + 1), pos(n + 1), base(n + 1);
    int timer = 0;
    vector<pair<int, int>> tasks = {{1, 1}};
    while (!tasks.empty()) {
        int start = tasks.back().first, h = tasks.back().second;
        tasks.pop_back();
        for (int u = start; u; u = heavy[u]) {
            head[u] = h;
            pos[u] = ++timer;
            base[timer] = a[u];
            for (int v : g[u]) if (v != parent[u] && v != heavy[u]) tasks.push_back({v, v});
        }
    }
    SegTree seg(base);
    auto path = [&](int u, int v) {
        Info left, right;
        while (head[u] != head[v]) {
            if (depth[head[u]] >= depth[head[v]]) {
                left = merge_info(left, reverse_info(seg.get(pos[head[u]], pos[u])));
                u = parent[head[u]];
            } else {
                right = merge_info(seg.get(pos[head[v]], pos[v]), right);
                v = parent[head[v]];
            }
        }
        if (depth[u] >= depth[v]) left = merge_info(left, reverse_info(seg.get(pos[v], pos[u])));
        else left = merge_info(left, seg.get(pos[u], pos[v]));
        return merge_info(left, right);
    };
    while (q--) {
        char type;
        cin >> type;
        if (type == 'C') {
            int x;
            cin >> x;
            a[x] = -a[x];
            seg.set(pos[x], a[x]);
        } else {
            int u, v, k;
            cin >> u >> v >> k;
            Info z = path(u, v);
            cout << (z.minsub <= k && k <= z.maxsub ? "YES" : "NO") << '\n';
        }
    }
    return 0;
}