Как поддержать DSU с весами/чётностью рёбер (взвешенный union-find), чтобы отвечать «X и Y одной группы или разных»?

Это DSU с потенциалами: помимо родителя храним rel[x] — отношение x к своему родителю (для двудольности это бит чётности: 0 — та же доля, 1 — другая). При сжатии путей пересчитываем rel как сумму (xor для чётности) вдоль пути.

struct DSUParity {
    vector<int> p, rel; // rel[x] = чётность пути x -> p[x] (0/1)
    DSUParity(int n): p(n), rel(n,0){ iota(p.begin(),p.end(),0); }
    pair<int,int> find(int x){ // {корень, чётность x->корень}
        if (x==p[x]) return {x,0};
        auto [r, pr] = find(p[x]);
        p[x]=r; rel[x]^=pr; // сжатие + накопление чётности
        return {r, rel[x]};
    }
    // d=0: A,B одной доли; d=1: разных. false => противоречие
    bool unite(int a, int b, int d){
        auto [ra, da] = find(a);
        auto [rb, db] = find(b);
        if (ra==rb) return (da ^ db) == d;
        p[ra]=rb; rel[ra] = da ^ db ^ d;
        return true;
    }
};

Идея: чётность между A и B = rel(A->корень) xor rel(B->корень). Если корни совпали — просто проверяем, что наблюдаемая чётность совпадает с заявленной d; если нет — противоречие. Если корни разные — подвешиваем и подбираем rel корня так, чтобы соотношение выполнилось. Сложность O(α(n)) амортизированно на запрос, память O(n). Для k>2 групп (как в «фуд-чейн») rel хранят по модулю k и используют сложение/вычитание вместо xor.