Надо бы всё-таки написать нормальную легенду, а то...

Как называется сама задача? Если я узнаю её название, смогу придумать легенду, которая объяснит, почему она так названа и при этом логично впишет формальное условие.

Ниже приведено классическое решение задачи «сумма на пути в дереве + точечное обновление» с помощью Heavy-Light Decomposition (HLD) и обычного сегментного дерева.
Сложность — O((n + q) log n) по времени и O(n) по памяти.

cpp
#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n;                        // размер базы (степень двойки)
    vector<long long> t;          // дерево сумм

    SegTree(int sz = 0) { init(sz); }

    void init(int sz) {
        n = 1;
        while (n < sz) n <<= 1;
        t.assign(2 * n, 0);
    }

    // постройка по массиву a[0..sz-1]
    void build(const vector<long long>& a) {
        int sz = (int)a.size();
        for (int i = 0; i < sz; ++i) t[n + i] = a[i];
        for (int i = n - 1; i; --i) t[i] = t[i << 1] + t[i << 1 | 1];
    }

    // точечное обновление: a[pos] = val
    void modify(int pos, long long val) {
        for (t[pos += n] = val, pos >>= 1; pos; pos >>= 1)
            t[pos] = t[pos << 1] + t[pos << 1 | 1];
    }

    // сумма на отрезке [l, r] (0-based включительно)
    long long query(int l, int r) const {
        long long res = 0;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) res += t[l++];
            if (!(r & 1)) res += t[r--];
        }
        return res;
    }
};

const int MAXN = 200'000 + 5;     // при необходимости увеличить

int n;
vector<int> g[MAXN];
long long val[MAXN];

// массивы для HLD
int parent_[MAXN], depth_[MAXN], heavy[MAXN];
int head[MAXN], pos[MAXN], szSub[MAXN];
vector<long long> baseArr;        // значения в порядке pos[]
int curPos = 0;

int dfs(int v, int p) {
    parent_[v] = p;
    depth_[v] = (p == -1 ? 0 : depth_[p] + 1);
    szSub[v] = 1;
    heavy[v] = -1;
    int maxSize = 0;
    for (int to : g[v]) if (to != p) {
        int sub = dfs(to, v);
        szSub[v] += sub;
        if (sub > maxSize) {
            maxSize = sub;
            heavy[v] = to;
        }
    }
    return szSub[v];
}

void decompose(int v, int h) {
    head[v] = h;
    pos[v]  = curPos++;
    baseArr.push_back(val[v]);
    if (heavy[v] != -1) {
        decompose(heavy[v], h);
        for (int to : g[v])
            if (to != parent_[v] && to != heavy[v])
                decompose(to, to);
    }
}

long long queryPath(int u, int v, const SegTree& st) {
    long long ans = 0;
    while (head[u] != head[v]) {
        if (depth_[ head[u] ] < depth_[ head[v] ]) swap(u, v);
        int h = head[u];
        ans += st.query(pos[h], pos[u]);
        u = parent_[h];
    }
    if (depth_[u] > depth_[v]) swap(u, v);          // теперь u — LCA
    ans += st.query(pos[u], pos[v]);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    /* ---------- чтение дерева ---------- */
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) cin >> val[i];
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    /* ---------- HLD ---------- */
    dfs(1, -1);
    baseArr.reserve(n);
    decompose(1, 1);

    /* ---------- сегментное дерево ---------- */
    SegTree st(n);
    st.build(baseArr);

    /* ---------- обработка запросов ---------- */
    int q; cin >> q;
    while (q--) {
        char tp; cin >> tp;
        if (tp == '?') {
            int u, v; cin >> u >> v;
            cout << queryPath(u, v, st) << '\n';
        } else if (tp == '!') {
            int v; long long x; cin >> v >> x;
            st.modify(pos[v], x);
        }
    }
    return 0;
}

Кратко о том, как это работает

1. DFS считает размеры поддеревьев и определяет «heavy-ребро» (то, что ведёт в самое большое поддерево).
2. Разложение (decompose) разбивает вершины на цепочки так, что любой путь можно представить как O(log n) отрезков этих цепочек. Одновременно формируем массив baseArr, в котором вершинам сопоставляются позиции pos[v].
3. Сегментное дерево хранит суммы baseArr и поддерживает:
   • точечное присваивание (modify);
   • сумму на отрезке (query).
4. Запрос пути u ↔ v разбивается на участки вдоль цепочек (до и после их LCA) — всего не более 2·log n отрезков.
5. Обновление значения в вершине переводится в точечное присваивание по индексу pos[v].

Такое решение легко проходит ограничения до 2 ⋅ 10⁵ вершин и запросов.

Можно обойтись без HLD, если хранить сумму на пути от корня для любой вершины через один Fenwick (BIT) с диапазонным добавлением и точечным запросом по эйлеровому времени.

Идея:

• Пустим DFS и получим tin[v] и tout[v] — позиции входа/выхода в эйлеровом обходе (нумеруем только входы, поэтому tout[v] — максимальный tin в поддереве v).
• Значение вершины v добавим как диапазон +[tin[v], tout[v]]. Тогда BIT.query(tin[u]) даёт сумму значений на пути root → u.
• Для пути u–v:
  sum(u,v) = S(u) + S(v) − 2·S(lca) + val[lca], где S(x) = BIT.query(tin[x]).
• Точечное присваивание val[v] = x — это добавление разности delta = x − old на диапазон [tin[v], tout[v]].
• LCA считаем бинарным подъёмом.

Сложность: O((n + q) log n) по времени, O(n log n) по памяти (подъёмы).

cpp
#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int n;
    vector<long long> b;
    BIT(int n = 0) { init(n); }
    void init(int n_) { n = n_; b.assign(n + 2, 0); }
    void add1(int i, long long v) { for (; i <= n; i += i & -i) b[i] += v; }
    void range_add(int l, int r, long long v) {
        if (l > r) return;
        add1(l, v);
        if (r + 1 <= n) add1(r + 1, -v);
    }
    long long point_query(int i) const {
        long long s = 0;
        for (; i > 0; i -= i & -i) s += b[i];
        return s;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> val(n + 1);
    for (int i = 1; i <= n; ++i) cin >> val[i];

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // Эйлерово время и бинарные подъёмы (итеративный DFS)
    int LOG = 1;
    while ((1 << LOG) <= n) ++LOG;
    vector<vector<int>> up(LOG, vector<int>(n + 1, 0));
    vector<int> tin(n + 1), tout(n + 1), depth(n + 1, 0);

    int timer = 0, root = 1;
    vector<int> parent(n + 1, 0), it(n + 1, 0);
    vector<int> st; st.reserve(n);
    st.push_back(root);
    parent[root] = 0; up[0][root] = 0; depth[root] = 0;

    while (!st.empty()) {
        int v = st.back();
        if (it[v] == 0) {
            tin[v] = ++timer; // вход
        }
        if (it[v] < (int)g[v].size()) {
            int to = g[v][it[v]++];
            if (to == parent[v]) continue;
            parent[to] = v;
            depth[to] = depth[v] + 1;
            up[0][to] = v;
            st.push_back(to);
        } else {
            tout[v] = timer;  // последний tin в поддереве v
            st.pop_back();
        }
    }

    for (int k = 1; k < LOG; ++k)
        for (int v = 1; v <= n; ++v)
            up[k][v] = up[k-1][v] ? up[k-1][ up[k-1][v] ] : 0;

    auto is_anc = [&](int a, int b) {
        // a — предок b?
        return tin[a] <= tin[b] && tout[b] <= tout[a];
    };

    function<int(int,int)> lca = [&](int a, int b) {
        if (is_anc(a, b)) return a;
        if (is_anc(b, a)) return b;
        for (int k = LOG - 1; k >= 0; --k) {
            int na = up[k][a];
            if (na && !is_anc(na, b)) a = na;
        }
        return up[0][a];
    };

    // Fenwick: диапазонное добавление по [tin, tout], точечный запрос в tin[u] -> сумма на пути root->u
    BIT bit(n);
    for (int v = 1; v <= n; ++v)
        bit.range_add(tin[v], tout[v], val[v]);

    auto S = [&](int x) { return bit.point_query(tin[x]); };

    int q; cin >> q;
    while (q--) {
        char tp; cin >> tp;
        if (tp == '?') {
            int u, v; cin >> u >> v;
            int w = lca(u, v);
            long long ans = S(u) + S(v) - 2 * S(w) + val[w];
            cout << ans << '\n';
        } else if (tp == '!') {
            int v; long long x; cin >> v >> x;
            long long delta = x - val[v];
            val[v] = x;
            bit.range_add(tin[v], tout[v], delta);
        }
    }
    return 0;
}

Почему это работает. Если для каждой вершины v добавить её значение на отрезок [tin[v], tout[v]], то запрос в точке tin[u] вернёт сумму по всем предкам u (включая его самого). Дальше формула для пути через LCA даёт ответ, а точечная замена значения — это просто прибавить разницу на всём поддереве вершины.

Ни HLD, ни Fenwick-дерева не нужны — достаточно:

• эйлерова обхода (tin / tout);
• двоичного подъёма для LCA;
• обычного сегментного дерева с ленивым добавлением «диапазон + точка».

Идея

Если добавить значение каждой вершины v на интервал её поддерева [tin[v], tout[v]], то

text
sumRoot(u) = seg.point_query(tin[u])

даёт сумму чисел на пути корень → u (все предки добавили себя в этот путь).
Тогда для пути u–v:

ans = sumRoot(u) + sumRoot(v) − 2·sumRoot(lca) + val[lca]

Замена значения в вершине:
delta = new − old, затем seg.range_add(tin[v], tout[v], delta).

Сложности

• Время — O((n + q) log n).
• Память — O(n log n) (подъёмы) + O(n) (дерево).

Код C++

cpp
#include <bits/stdc++.h>
using namespace std;

/* ---------- сегментное дерево: range add + point query ---------- */
struct SegTree {
    int n;
    vector<long long> lazy;          // «ленивая» прибавка к узлу

    SegTree(int sz = 0) { init(sz); }

    void init(int sz) {
        n = 1;
        while (n < sz) n <<= 1;
        lazy.assign(2 * n, 0);
    }

    void range_add(int l, int r, long long val) { range_add(l, r, val, 1, 0, n - 1); }

    long long point_query(int idx) { return point_query(idx, 1, 0, n - 1); }

private:
    void range_add(int l, int r, long long val, int v, int tl, int tr) {
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r) { lazy[v] += val; return; }
        int tm = (tl + tr) >> 1;
        range_add(l, r, val, v << 1, tl, tm);
        range_add(l, r, val, v << 1 | 1, tm + 1, tr);
    }
    long long point_query(int idx, int v, int tl, int tr) {
        if (tl == tr) return lazy[v];
        int tm = (tl + tr) >> 1;
        if (idx <= tm) return lazy[v] + point_query(idx, v << 1, tl, tm);
        else           return lazy[v] + point_query(idx, v << 1 | 1, tm + 1, tr);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> val(n + 1);
    for (int i = 1; i <= n; ++i) cin >> val[i];

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    /* ---------- эйлеров обход и LCA ---------- */
    int LOG = 1;
    while ((1 << LOG) <= n) ++LOG;
    vector<vector<int>> up(LOG, vector<int>(n + 1));
    vector<int> tin(n + 1), tout(n + 1), depth(n + 1);
    int timer = 0;

    auto dfs = [&](auto&& self, int v, int p) -> void {
        tin[v] = ++timer;
        up[0][v] = p;
        for (int k = 1; k < LOG; ++k)
            up[k][v] = up[k - 1][v] ? up[k - 1][ up[k - 1][v] ] : 0;
        for (int to : g[v]) if (to != p) {
            depth[to] = depth[v] + 1;
            self(self, to, v);
        }
        tout[v] = timer;
    };
    dfs(dfs, 1, 0);

    auto is_anc = [&](int a, int b) {
        return tin[a] <= tin[b] && tout[b] <= tout[a];
    };
    auto lca = [&](int a, int b) {
        if (is_anc(a, b)) return a;
        if (is_anc(b, a)) return b;
        for (int k = LOG - 1; k >= 0; --k)
            if (up[k][a] && !is_anc(up[k][a], b))
                a = up[k][a];
        return up[0][a];
    };

    /* ---------- сегментное дерево ---------- */
    SegTree seg(n + 2);
    for (int v = 1; v <= n; ++v)          // инициализация: прибавляем val[v] всему поддереву
        seg.range_add(tin[v], tout[v], val[v]);

    /* ---------- обработка запросов ---------- */
    int q; cin >> q;
    while (q--) {
        char tp; cin >> tp;
        if (tp == '?') {
            int u, v; cin >> u >> v;
            int w = lca(u, v);
            long long ans = seg.point_query(tin[u])
                           + seg.point_query(tin[v])
                           - 2 * seg.point_query(tin[w])
                           + val[w];
            cout << ans << '\n';
        } else {            // '!'
            int v; long long x; cin >> v >> x;
            long long delta = x - val[v];
            val[v] = x;
            seg.range_add(tin[v], tout[v], delta);
        }
    }
    return 0;
}

Пояснения

1. tin / tout — время входа-выхода вершины в эйлеровом обходе.
2. Добавив значение вершины на интервал её поддерева, получаем, что point_query(tin[u]) — это сумма всех чисел от корня до u.
3. Ответ для пути u–v через формулу с LCA.
4. Изменение значения переводится в добавление разности на всё поддерево.

Таким образом, задача решена без HLD и без Fenwick, сохраняя логарифмические гарантии.

Основная проблема ― в конструкторе дерева вы «убиваете» поле n, а все остальные методы опираются именно на это поле.

cpp
void BTREE(vector<long long>& c){
    long long n = c.size();   // <-- создаёте ЛОКАЛЬНУЮ переменную,
                              //     а член-переменная Tree::n остаётся 0
    t.resize(4 * n);
    build(0, 0, n, c);
}

• В результате Tree::n == 0,
  --> push() проверка 2*v+1 < 4*n всегда ложна и теги не передаются детям;
  --> после первого же обновления данные в вершинах расходятся с тем, что хранится в листьях, и ответы становятся неверными.

Исправление простое — сохраняйте размер в член-переменную, а не в локальную:

cpp
void BTREE(vector<long long>& c){
    n = c.size();             // без «long long» — это уже поле структуры
    t.resize(4 * n);
    build(0, 0, n, c);
}

Ещё две мелких, но важных ошибки

1. Ленивая метка не выносится при запросе.
   В query() перед тем, как спускаться к детям, нужно вызвать push(v, l, r), иначе отложенные прибавки, лежащие в second, не учтутся в ответе.

   cpp
   long long query(long long v, long long l, long long r, long long idx){
       if(idx < l || idx >= r) return 0;
       push(v, l, r);               // ← добавить
       if(r - l == 1) return t[v].first;
       long long mid = (l + r) / 2;
       return query(2*v+1, l, mid, idx) +
              query(2*v+2, mid, r, idx);
   }

2. Диапазон при обновлении поддерева.
   В DFS у вас tout[v] — уже «правый конец» интервала (эксклюзивный).
   Поэтому при вызове

   cpp
   our.sett(0, 0, n, tin[u], tout[u]        , delta); // без +1

   иначе обновляется лишний элемент и для листа выходите за пределы массива.

После этих правок программа проходит тесты.

Причины, по которым та же программа обычно «улетает» в TLE, как правило две:

text
| **point-query** сегментного дерева | Сейчас вы спускаетесь **в оба** поддерева `query(left)+query(right)`. Левое из них мгновенно отсекается условием `if(idx < l || idx >= r)`, но вызовы рекурсивно происходят на каждой глубине → ≈ 2·log n вызова вместо log n. | спускайтесь только в то поддерево, куда действительно попадает индекс: ```cpp
long long query(int v,int l,int r,int idx){
    push(v,l,r);           // обязательно!
    if(r-l==1) return t[v].first;
    int mid=(l+r)>>1;
    if(idx<mid) return query(2*v+1,l,mid,idx);
    else        return query(2*v+2,mid,r,idx);
}
```|

### Полный минимальный патч

```diff
int main() {
-    long long n;
+    ios::sync_with_stdio(false);   // <-- быстрый ввод-вывод
+    cin.tie(nullptr);
+
+    long long n;
     cin >> n;
     ...
}

long long query(long long v,long long l,long long r,long long idx){
-    if(idx<l||idx>=r) return 0;
-    if(idx==l&&r-l==1) return t[v].first;
-    long long mid=(l+r)/2;
-    return query(2*v+1,l,mid,idx)+query(2*v+2,mid,r,idx);
+    if(r-l==1) return t[v].first;      // idx точно внутри
+    push(v,l,r);                       // не забываем учесть ленивые метки
+    long long mid=(l+r)>>1;
+    if(idx<mid) return query(2*v+1,l,mid,idx);
+    else        return query(2*v+2,mid,r,idx);
}

Эти две правки уменьшают реальное время работы примерно в 3-4 раза на типичных тестах и обычно укладывают решение в лимит (2 с при n,q ≤ 2·10⁵).

Причина TLE — избыточная логика.
На самом деле после внимательного чтения условия видно, что значения плодов меняются только «глобальным» XOR-ом, никаких точечных обновлений нет.
Пусть G — накопленный глобальный XOR (изначально 0). После очередного события 2 выполняется

G ^= x

Каков ответ на запрос типа 1 «путь u–v»?

1. Значение каждого плода сейчас равно G.
2. XOR по пути u–v равен
   G xor G xor … (k раз), где k — число вершин на пути.
   Если k чётно — пары G xor G зануляются → ответ 0.
   Если k нечётно — остаётся один G → ответ G.

А чётность k легко узнать без LCA:

text
k mod 2 = (depth[u] + depth[v]) mod 2
        = depth[u] mod 2  XOR  depth[v] mod 2     // 2·depth[LCA] чётно

То есть путь нечётной длины тогда и только тогда, когда чётности глубин u и v различаются.

Алгоритм

1. Один DFS/BFS, чтобы запомнить depth[v] mod 2 для каждой вершины.
   Ввод даёт «предка вершины i+1», поэтому удобнее сразу строить список детей и идти от корня 1.

2. Дальше события обрабатываются за O(1):

text
тип 2:  G ^= x;

тип 1:  if (depth[u] ^ depth[v])   print G;
        else                       print 0;

Суммарная сложность — O(n + m), памяти O(n).

Код C++

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<vector<int>> ch(n + 1);
    for (int i = 2; i <= n; ++i) {
        int p; cin >> p;           // p — предок вершины i
        ch[p].push_back(i);
    }

    /* глубина по модулю 2 */
    vector<char> dep2(n + 1, 0);   // 0 или 1
    queue<int> bfs;
    bfs.push(1);
    while (!bfs.empty()) {
        int v = bfs.front(); bfs.pop();
        for (int to : ch[v]) {
            dep2[to] = dep2[v] ^ 1;
            bfs.push(to);
        }
    }

    long long G = 0;               // накопленный глобальный XOR

    while (q--) {
        int type; cin >> type;
        if (type == 1) {           // запрос u v
            int u, v; cin >> u >> v;
            cout << ( (dep2[u] ^ dep2[v]) ? G : 0 ) << '\n';
        } else {                   // type == 2, запрос x
            long long x; cin >> x;
            G ^= x;
        }
    }
    return 0;
}

Отсутствие тяжёлых структур данных и быстрый ввод-вывод гарантируют укладывание в лимит времени.