[CF342E] Xenia and Tree

[CF342E] Xenia and Tree - 分块,ST表,LCA

Description

给定一颗 (n) 个结点的树，初始时 (1) 号结点为红色，其余为蓝色。要求支持将一个结点变为红色，或者询问一个点到最近的红色点的距离。

Solution

对整个操作序列分块，则所有的影响分为块间的和块内的。块内的用 ST 表 LCA 来处理，块间的预处理好，即每处理完一个块，我们就用 BFS 计算好这个块的后续影响。复杂度 (O(n sqrt n))

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int n, m;
vector<int> g[N];

namespace _lca
{
    int rt, st[N][20], dep[N], dis[N], vis[N], ind, lg2[N], s[N], bg[N], ed[N];

    void dfs(int p)
    {
        vis[p] = 1;
        s[++ind] = p;
        bg[p] = ind;
        for (int q : g[p])
        {
            if (vis[q] == 0)
            {
                dep[q] = dep[p] + 1;
                dfs(q);
                s[++ind] = p;
            }
        }
        ed[p] = ind;
    }

    int lca(int p, int q)
    {
        if (p == q)
            return p;
        p = bg[p];
        q = bg[q];
        if (p > q)
            swap(p, q);
        int l = lg2[q - p + 1];
        int x = st[p][l];
        int y = st[q - (1 << l) + 1][l];
        return s[dis[x] < dis[y] ? x : y];
    }

    int dist(int p, int q)
    {
        int l = lca(p, q);
        return dep[p] + dep[q] - 2 * dep[l];
    }

    void solve()
    {
        rt = 1;
        for (int i = 0; i <= 18; i++)
            for (int j = 1 << i; j < 1 << (i + 1); j++)
                lg2[j] = i;
        dfs(rt);
        for (int i = 1; i <= ind; i++)
            dis[i] = dep[s[i]];
        for (int i = 1; i <= ind; i++)
            st[i][0] = i;
        for (int i = 1; i <= 17; i++)
        {
            for (int j = 1; j <= ind; j++)
            {
                st[j][i] = dis[st[j][i - 1]] < dis[st[j + (1 << (i - 1))][i - 1]] ? st[j][i - 1] : st[j + (1 << (i - 1))][i - 1];
            }
        }
    }
} // namespace _lca

int get_dist(int p, int q)
{
    return _lca::dist(p, q);
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 1; i < n; i++)
    {
        int t1, t2;
        cin >> t1 >> t2;
        g[t1].push_back(t2);
        g[t2].push_back(t1);
    }

    _lca::solve();

    int b = sqrt(m);

    vector<int> buf;
    vector<int> dis(n + 2);

    for (int i = 1; i <= n; i++)
    {
        dis[i] = 1e18;
    }

    buf.push_back(1);

    for (int i = 1; i <= m; i++)
    {
        int type, v;
        cin >> type >> v;
        if (type == 1)
        {
            buf.push_back(v);
        }
        else
        {
            int ans = dis[v];
            for (auto p : buf)
            {
                ans = min(ans, get_dist(p, v));
            }
            cout << ans << endl;
        }
        if (i % b == 0)
        {
            queue<int> que;
            for (auto p : buf)
            {
                que.push(p);
                dis[p] = 0;
            }
            buf.clear();

            while (que.size())
            {
                int p = que.front();
                que.pop();

                for (auto q : g[p])
                {
                    if (dis[q] > dis[p] + 1)
                    {
                        dis[q] = dis[p] + 1;
                        que.push(q);
                    }
                }
            }

        }
    }
}