Дано дерево из n вершин. На каждой вершине дерева...

У тебя в коде сломана сама “смысловая” величина, которую ты хранишь в xr[] и в st[].

1) xr[u] у тебя не является префиксным XOR

Ты делаешь:

cpp
xr[u] ^= val[u];

но не передаёшь XOR от родителя. В итоге xr[u] после DFS почти всегда просто val[u] (или мусор от swap’ов), а не XOR по пути от корня/от текущей вершины. Отсюда все формулы вида vl ^ xr[v] ^ xr[u] становятся бессмысленными.

Если ты хотел префикс от корня, должно быть что-то вроде:

cpp
xr[u] = xr[p] ^ val[u];

(или передавать текущий XOR параметром).

---

2) Неправильно “переводишь” значения из поддерева ребёнка к текущей вершине

Правильная DSU-логика для этой задачи обычно такая:

• Корнем считаем 1.
• Для каждой вершины u храним множество st[u] значений
  XOR по пути от u до x, не включая u (для x в поддереве u).
• Тогда для пути с LCA = u условие “вес = 0” превращается в: $$t_x \oplus t_y = a[u]$$ где t_* — элементы из st[u].

При мердже ребёнка v в u нужно преобразовать все значения из v: если в st[v] лежит XOR от v вниз, то относительно u это будет (t ^ a[v]) (потому что путь от u вниз проходит через v и включает a[v]).

И проверка конфликта: для каждого x = t ^ a[v] надо проверить, есть ли в текущем st[u] значение x ^ a[u].

---

3) Когда нашёл конфликт, st[u].clear() недостаточно

После “починки” вершины u (ты увеличиваешь ans) поддерево выше должно видеть, что от u “торчат” только нулевой путь длины 0 (то есть u как точка). Поэтому нужно делать:

cpp
st[u].clear();
st[u].insert(0);

(у тебя вставка 0 есть только в начале DFS, но после clear её нет).

---

Как это выглядит в рабочем виде (минимальная правка идеи)

cpp
function<void(int,int)> dfs = [&](int u, int p){
    st[u].clear();
    st[u].insert(0);          // t(u)=0 (путь от u до u, не включая u)

    bool bad = false;

    for(int v: g[u]) if(v!=p){
        dfs(v,u);

        if(st[u].size() < st[v].size())
            st[u].swap(st[v]);

        // переносим значения из v к u: x = t ^ a[v]
        for(int t: st[v]){
            int x = t ^ val[v];

            // хотим найти y в st[u], что x ^ y == a[u]  <=> y == x ^ a[u]
            if(st[u].count(x ^ val[u])) bad = true;

            st[u].insert(x);
        }
        st[v].clear();
    }

    if(bad){
        ans++;
        st[u].clear();
        st[u].insert(0);  // после замены значения в u считаем, что наружу “выходит” только u
    }
};

---

Коротко: что именно “не так” в твоём коде

1. xr[] не считается как нужно (нет накопления от родителя).
2. Формулы при мердже множества неправильные: ты мешаешь xr[u], xr[v], val[u] без корректной интерпретации.
3. После st[u].clear() ты теряешь базовый 0, из-за чего наверху начинает ломаться логика.

---

Если хочешь — могу прямо на твоём исходнике сделать минимальный diff (сохранить set<int>, твой DSU swap и т.п.), чтобы он стал корректным и проходил ограничения 2e5.

Да, я понял идею: в set ты хранишь “какие XOR-значения могут получиться на путях вниз”.

Но проблема в том, что ты неправильно пересчитываешь эти значения при подъёме вверх.

---

Что именно должно храниться в st[u]

Если ты хочешь DSU-on-tree, то удобно хранить так:

st[u] = все значения XOR на путях от u до вершины x в его поддереве, но без a[u].

Тогда:

• 0 всегда есть (путь u -> u, пустой по вершинам кроме u).
• если ребёнок v дал значение t (XOR от v до x без a[v]),
  то относительно u это будет t ^ a[v].

---

Как проверять “плохой путь”

Плохой путь с LCA = u существует, если есть две вершины x и y из разных поддеревьев такие что:

$$(path(u \to x)) \oplus (path(u \to y)) \oplus a[u] = 0$$

Если st[u] хранит XOR от u вниз без a[u], то условие становится:

$$t_x \oplus t_y = a[u]$$

То есть для каждого t_x надо проверить наличие t_y = t_x ^ a[u].

---

Что у тебя не так

Ты пытаешься делать это через:

cpp
vl ^ xr[v] ^ xr[u]

но:

❌ xr[u] у тебя не означает XOR пути

Ты делаешь:

cpp
xr[u] ^= val[u];

но не учитываешь родителя → это почти всегда просто val[u], а не путь.

Поэтому ты складываешь какие-то случайные числа, которые не являются XOR путей.

---

Главная ошибка в твоей логике

Ты думаешь:

"в set лежат возможные значения, значит я их как-то XOR-ну и получу новые"

Но пересчёт должен быть строго:

если переносишь значение из ребёнка v к u:

cpp
new_value = old_value ^ val[v];

А проверка конфликта:

cpp
if (st[u] contains (new_value ^ val[u])) -> bad

---

Ещё одна ошибка

Ты делаешь:

cpp
if (bad) {
    ans++;
    st[u].clear();
}

Но после очистки надо вернуть базу:

cpp
st[u].clear();
st[u].insert(0);

иначе родитель получит пустое множество и всё развалится.

---

Итог

Твой set — нормальная идея, но:

• xr[] вообще не нужен
• формулы vl ^ xr[v] ^ xr[u] ^ val[u] неверны
• перенос должен быть только ^ val[child]
• после фикса вершины set должен стать {0}

---

Если хочешь, я могу переписать твой код в том же стиле (DSU swap + set) так, чтобы он был корректным и проходил 2e5.