how to find sum of values on path in atree

1#include <bits/stdc++.h>
2#define FOR(i, x, y) for (int i = x; i < y; i++)
3typedef long long ll;
4using namespace std;
5
6int n, m;
7
8vector<int> graph[100001];
9int timer = 1, tin[100001], tout[100001];
10int anc[100001][18];
11
12void dfs(int node = 1, int parent = 0) {
13    anc[node][0] = parent;
14    for (int i = 1; i < 18 && anc[node][i - 1]; i++)
15        anc[node][i] = anc[anc[node][i - 1]][i - 1];
16
17    tin[node] = timer++;
18    for (int i : graph[node]) if (i != parent) dfs(i, node);
19    tout[node] = timer;
20}
21
22int bit[100001];
23
24void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }
25
26int query(int pos) {
27    int ans = 0;
28    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
29    return ans;
30}
31
32int find_ancestor(int node) {
33    int lca = node;
34    for (int i = 17; ~i; i--) {
35        if (anc[lca][i] && query(tin[anc[lca][i]]) == query(tin[node])) lca = anc[lca][i];
36    }
37    return lca;
38}
39
40int main() {
41    ios_base::sync_with_stdio(0);
42    cin.tie(0);
43    freopen("disconnect.in", "r", stdin);
44    freopen("disconnect.out", "w", stdout);
45    cin >> n >> m;
46    FOR(i, 1, n) {
47        int a, b;
48        cin >> a >> b;
49        graph[a].push_back(b);
50        graph[b].push_back(a);
51    }
52    dfs();
53
54    int v = 0;
55    while (m--) {
56        int t, x, y;
57        cin >> t >> x >> y;
58        int a = x ^ v, b = y ^ v;
59
60        if (t == 1) {
61            if (anc[b][0] == a) swap(a, b);
62            update(tin[a], 1);
63            update(tout[a], -1);
64        } else {
65            if (find_ancestor(a) == find_ancestor(b)) {
66                cout << "YES\n";
67                v = a;
68            } else {
69                cout << "NO\n";
70                v = b;
71            }
72        }
73    }
74    return 0;
75}
76