without HLD range Quey can be handled by just using segment tree on the FLATTENED TREE (euler tour), C++ (gcc)

without HLD range Quey can be handled by just using segment tree on the FLATTENED TREE (euler tour)

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
typedef long double ld;
typedef long long int ll;

const int N = 3e5 + 5;

const ll inf = (ll)2e18 + 10;

const int mod = 1e9 + 7;

struct seg_tree{
    int *seg, n;
    
    seg_tree(int x) : n(x){
        seg = new int[4*n];
        for(int j = 0; j <4*n; j++) seg[j]  = 0;
    }
    
    void update(int pos, int val, int l = 0, int r = -1, int i = 0){
        if(r == -1) r += n;
        if(l == r){
            seg[i] = val;
            return;
        }
        int m = (l+r) >> 1;
        if(m >= pos) update(pos, val, l, m, i*2+1);
        else update(pos, val, m+1, r ,i*2+2);
        seg[i] = seg[i*2+1] + seg[i*2+2];
    }
    
    int query(int x, int y, int l = 0, int r = -1, int i = 0){
        if(r == -1) r += n;
        if(r < x || l > y) return 0;
        if(l >= x && r <= y) return seg[i];
        int m = (l+r) >> 1;
        return (query(x, y, l, m, i*2+1) + query(x, y, m+1, r, i*2+2));
    }
};

int timer = 0, st[N], ed[N], id[N], lvl[N], dp[20][N], n;

vector<int> g[N];

void dfs(int s, int p){
    st[s] = timer++;
    lvl[s] = lvl[p] + 1;
    dp[0][s] = p;
    for(int j = 1; j < 20; j++) dp[j][s] = dp[j-1][dp[j-1][s]];
    
    for(auto i : g[s])
        if(i != p) dfs(i, s);
    
    ed[s] = timer++;
}

seg_tree *s;

void build(){
    lvl[0] = 0;
    for(int j = 0; j < 20; j++) dp[j][0] = 0;
    dfs(1, 0);
    
    s = new seg_tree(2*n);
    for(int j = 1; j <= n; j++) s -> update(st[j], id[j]), s -> update(ed[j], -id[j]);
}

int LCA(int u, int v){
    if(lvl[u] > lvl[v]) swap(u, v);
    int df = lvl[v] - lvl[u];
    for(int j = 19; j >= 0; j--)
        if(df >= (1 << j)) df -= (1 << j), v = dp[j][v];
    if(u == v) return u;
    
    for(int j = 19; j >= 0; j--)
        if(dp[j][u] != dp[j][v]) u = dp[j][u], v = dp[j][v];
    return dp[0][v];
}

bool query(int u, int v){
    if(lvl[u] > lvl[v]) swap(u, v);
    int lca = LCA(u, v), sum = 0;
    if(lca == u){
        sum = s -> query(st[u], st[v]);
    }
    else{
        sum = s -> query(st[lca], st[u]) + s -> query(st[lca], st[v]) - id[lca];
    }
    return (sum == 0 || sum == (lvl[u] + lvl[v] - 2*lvl[lca] + 1));
}

void flip(int i){
    id[i] ^= 1;
    s -> update(st[i], id[i]);
    s -> update(ed[i], -id[i]);
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    int q;
    scanf("%d %d",&n ,&q);
    char s[N];
    scanf("%s",&s);
    for(int j = 1; j <= n; j++) id[j] = s[j-1] - '0';
    for(int j = 0; j < n-1; j++){
        int u, v;
        scanf("%d %d",&u ,&v);
        u++, v++;
        g[u].pb(v);
        g[v].pb(u);
    }
    build();
    
    while(q--){
        int t;
        scanf("%d",&t);
        if(t == 1){
            int u, v;
            scanf("%d %d",&u ,&v);
            u++, v++;
            if(query(u, v)) cout << "YES\n";
            else cout << "NO\n";
        }
        else{
            int x;
            scanf("%d",&x);
            x++;
            flip(x);
        }
    }
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development