题解 | 2023 年牛客多校第三场 I 题

题意：有一个 $nn$ 个点的树，第 $ii$ 个点拥有的颜色种类由二进制数 $c_{i}c\_i$ 定义。$qq$ 次询问，每次从 $uu$ 出发到 $vv$，初始自选颜色，一秒的时间里可以移动到相邻同色节点（即该节点有自身的一种颜色），或者在一个点变换自身颜色（必须是这个点已经有的颜色）。问花费的最少时间。$1\le n,q\le 5\times 10^{5}1\; \backslash le\; n,q\; \backslash le\; 5\backslash times\; 10^5$，。

解法：一个贪心的想法是，能尽可能维持当前颜色不变就尽可能不变。因而首先处理出从当前节点 $uu$ 向上最多能不变色走到哪里，然后再倍增处理出变 $2^{k}2^k$ 次颜色会跳到哪里（因为可能不变色一次只能走一条边）。

考虑 $u\to vu\; \backslash to\; v$ 可以拆分成 $u\to \mathrm{l}\mathrm{c}\mathrm{a}(u,v)\to vu\; \backslash to\; \{\backslash rm\; lca\}(u,v)\; \backslash to\; v$，因而拆分成祖孙链上的问题。对于单程 $u\to \mathrm{l}\mathrm{c}\mathrm{a}(u,v)u\; \backslash to\; \{\backslash rm\; lca\}(u,v)$，首先倍增跳到最靠近 $\mathrm{l}\mathrm{c}\mathrm{a}(u,v)\{\backslash rm\; lca\}(u,v)$ 的变色点 $ww$，然后再维护不变色段 $w\to \mathrm{l}\mathrm{c}\mathrm{a}(u,v)w\; \backslash to\; \{\backslash rm\; lca\}(u,v)$ 的可行颜色，对 $vv$ 做同样的考虑。两侧取交集非空则不需要在转折点变色。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
vector<int> ve[maxn];
int dep[maxn], f[21][maxn];
int jmp[21][maxn];
int col[60][maxn]; // 对于每个颜色能跳的最高的节点
long long a[maxn];
int Fa[maxn];
void dfs(int x, int fa)
{
    dep[x] = dep[fa] + 1;
    Fa[x] = fa;
    int up = -1;
    for (int i = 0; i < 60; i++)
    {
        col[i][x] = col[i][fa];
        if ((a[x] >> i & 1) && col[i][x] == -1)
            col[i][x] = x;
        if (~a[x] >> i & 1)
            col[i][x] = -1;
        if (up == -1 || (col[i][x] != -1 && dep[up] > dep[col[i][x]]))
            up = col[i][x];
    }
    jmp[0][x] = up;
    for (int i = 0; i <= 19; i++)
    {
        f[i + 1][x] = f[i][f[i][x]];
        if (jmp[i][x] != -1)
            jmp[i + 1][x] = jmp[i][jmp[i][x]];
    }
    for (auto it : ve[x])
    {
        if (it == fa)
            continue;
        f[0][it] = x;
        dfs(it, x);
    }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
    {
        if (dep[f[i][x]] >= dep[y])
            x = f[i][x];
        if (x == y)
            return x;
    }
    for (int i = 20; i >= 0; i--)
        if (f[i][x] != f[i][y])
            x = f[i][x], y = f[i][y];
    return f[0][x];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    memset(col, -1, sizeof(col));
    memset(jmp, -1, sizeof(jmp));
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        ve[x].push_back(y);
        ve[y].push_back(x);
    }
    dfs(1, 0);
    function<int(int, int)> solve = [&](int x, int y)
    {
        int L = lca(x, y);
        int ans = dep[x] + dep[y] - dep[L] * 2;
        if (x == L)
            swap(x, y);
        if (x == L)
            return 0;
        if (y == L)
        {
            for (int i = 20; i >= 0; i--)
                if (jmp[i][x] != -1 && dep[jmp[i][x]] > dep[L])
                {
                    ans += 1 << i;
                    x = jmp[i][x];
                }
            if (a[x] & a[Fa[x]])
                return ans;
            return -1;
        }
        for (int i = 20; i >= 0; i--)
            if (jmp[i][x] != -1 && dep[jmp[i][x]] > dep[L])
            {
                ans += 1 << i;
                x = jmp[i][x];
            }
        for (int i = 20; i >= 0; i--)
            if (jmp[i][y] != -1 && dep[jmp[i][y]] > dep[L])
            {
                ans += 1 << i;
                y = jmp[i][y];
            }
        if (jmp[0][x] == -1 || jmp[0][y] == -1)
            return -1;
        if (dep[jmp[0][x]] > dep[L] || dep[jmp[0][y]] > dep[L])
            return -1;
        bool flag = false;
        for (int i = 0; i < 60; i++)
            if (col[i][x] != -1 && col[i][y] != -1)
            {
                if (dep[col[i][x]] <= dep[L] && dep[col[i][y]] <= dep[L])
                    flag = true;
            }
        if (flag)
            return ans;
        else
            return ans + 1;
    };
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        cout << solve(x, y) << "\n";
    }
    return 0;
}