Subtask 1

Đối với mỗi truy vấn hỏi khoảng cách, ta sẽ thực hiện một lần BFS / DFS để tìm khoảng cách tới đỉnh màu đỏ gần nhất.

Độ phức tạp: ~O(n \cdot m)~

Subtask 2

Ta sẽ thực hiện một lần BFS đa nguồn sau khi đã đánh dấu lại các đỉnh được tô màu đỏ. Sau đó với mỗi truy vấn, ta sẽ trả lời trong ~O(1)~.

Độ phức tạp: ~O(n + m)~

Subtask 3

Ta sử dụng Centroid Tree trong bài viết về Centroid Decomposition của VNOI để giải quyết bài toán này.

Điểm mấu chốt của bài toán là ở tính chất thứ ba của Centroid Tree trong bài viết, "~LCA(u, v)~ trên cây trọng tâm cũng thuộc đường đi của ~u, v~ trên cây ban đầu". Do đó, khi tô một đỉnh màu đỏ, ta sẽ cập nhật khoảng cách của đỉnh này tới các cha của nó và ta sẽ làm tương tự khi trả lời truy vấn ~2~.

Vì độ cao tối đa của cây Centroid không vượt quá ~log(n)~ nên độ phức tạp của ta sẽ là ~O((n + m) \cdot \log n)~

Độ phức tạp : ~O((n + m) \cdot \log n)~

Ngoài ra, bài này cũng tồn tại một solution khác sử dụng chia căn truy vấn và ~LCA\ O(1)~. Tuy nhiên, chúng mình sẽ không nói thêm về solution này tại đây.

#include <bits/stdc++.h>
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int N = 1e5 + 5, INF = 1e9 + 5, MOD = 1e9 + 7;
int n, q, sz[N], ans[N], par[N];
int tpar[17][N], h[N];
bool removed[N], red[N];
vector<int> adj[N];
void init(int i, int pre){
    for(int x : adj[i]){
        if(x == pre) continue;
        tpar[0][x] = i, h[x] = h[i] + 1;
        for(int j = 1; j < 17; j++) tpar[j][x] = tpar[j - 1][tpar[j - 1][x]];
        init(x, i);
    }
}
int dfs(int i, int pre){
    sz[i] = 1;
    for(int x : adj[i]){
        if(x == pre || removed[x]) continue;
        sz[i] += dfs(x, i);
    }
    return sz[i];
}
int find_centroid(int i, int pre, int targ){
    for(int x : adj[i]){
        if(x == pre || removed[x] || sz[x] * 2 <= targ) continue;
        return find_centroid(x, i, targ);
    }
    return i;
}
void centroid(int i, int pre){
    int cent = find_centroid(i, pre, dfs(i, 0));
    par[cent] = pre, removed[cent] = true;
    ans[cent] = INF;
    for(int x : adj[cent]){
        if(removed[x]) continue;
        centroid(x, cent);
    }
}
int lca(int x, int y){
    if(h[x] < h[y]) swap(x, y);
    int dist = h[x] - h[y];
    for(int i = 0; i < 17; i++){
        if(dist & (1 << i)) x = tpar[i][x];
    }
    if(x == y) return x;
    for(int i = 16; i >= 0; i--){
        if(tpar[i][x] != tpar[i][y]) x = tpar[i][x], y = tpar[i][y];
    }
    return tpar[0][x];
}
int dist(int x, int y){
    int p = lca(x, y);
    return h[x] + h[y] - 2 * h[p];
}
void upd(int i){
    int x = i;
    while(x > 0){
        int d = dist(i, x);
        ans[x] = min(ans[x], d);
        x = par[x];
    }
}
int query(int i){
    int res = INF, x = i;
    while(x > 0){
        int d = dist(x, i);
        res = min(res, ans[x] + d);
        x = par[x];
    }
    return res;
}
signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> q;
    for(int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    init(1, 1);
    centroid(1, 0);
    upd(1);
    while(q--){
        int type, x; cin >> type >> x;
        if(type == 1){
            red[x] = true; upd(x);
        }
        else{
            int res = query(x);
            cout << res << '\n';
        }
    }
    return 0;
}