5916번: Grass Planting

https://www.acmicpc.net/problem/5916

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100000, LGN = 16;
int n, m, cnt;
int bit[2 * MAX_N + 1], l[MAX_N + 1], r[MAX_N + 1], dp[MAX_N + 1][LGN + 1], lv[MAX_N + 1];
bool ck[MAX_N + 1];
vector<int> adj[MAX_N + 1];
void f(int h) {
    ck[h] = true;
    l[h] = ++cnt;
    for (auto it : adj[h]) {
        if (ck[it]) continue;
        lv[it] = lv[h] + 1;
        dp[it][0] = h;
        for (int i = 1; i <= LGN; i++)
            dp[it][i] = dp[dp[it][i - 1]][i - 1];
        f(it);
    }
    r[h] = ++cnt;
}
int lca(int x, int y) {
    if (lv[x] < lv[y]) swap(x, y);
    for (int i = LGN; i >= 0; i--)
        if (1 << i <= lv[x] - lv[y]) x = dp[x][i];
    if (x == y) return x;
    for (int i = LGN; i >= 0; i--)
        if (dp[x][i] != dp[y][i])
            x = dp[x][i], y = dp[y][i];
    return dp[x][0];
}
void update(int h, int s) {
    for (; h <= 2 * n; h += h&-h) bit[h] += s;
}
int query(int h) {
    int s = 0;
    for (; h; h -= h&-h) s += bit[h];
    return s;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    f(1);
    for (int i = 0; i < m; i++) {
        char c;
        int a, b;
        scanf(" %c %d %d", &c, &a, &b);
        if (c == 'P') {
            update(r[a], 1);
            update(r[b], 1);
            update(r[lca(a, b)], -2);
        }
        else {
            if (dp[a][0] != b) swap(a, b);
            printf("%d\n", query(r[a]) - query(l[a]));
        }
    }
    return 0;
}