前言

如何评价我场上 LCA 没清空 fa 数组没有 AK。

题目翻译

给定 $n$ 个点的一棵树，以及 $k$ 组点 $(u,v)$，表示 $u\to v$ 的简单路径包含特殊边。问至少多少边为特殊边。

多测，$1\leq t\leq 10^4,\sum n\leq10^5,\sum 2^k\leq 2^{20}$。

题目思路

$k$ 很小，考虑状压。$S_i$ 为一个 mask 表示第 $i$ 条边可能出现哪几条特殊边，也就是被哪几个路径包含。

设计 dp 状态 $f_{mask}$ 表示『包含集合 $mask$ 至少需要多少条边』。

直接转移是 $\mathcal O(2^k\times n)$ 的，无法通过。

发现 $k$ 条边至多 $2k$ 个点，直接建虚树大小为 $\mathcal O(k)$。所以我们建立虚树转移 dp。

我们直接对于 $S_i$ 进行去重，得到的集合大小只有 $\mathcal O(k)$ 了。现在复杂度为 $\mathcal O(2^k\times k)$，可以通过。

状压部分的染色，$u\to v$ 的简单路径就是 $u\to \operatorname{lca}(u,v)$ 加上 $v\to \operatorname{lca}(u,v)$，因此暴力跳 $fa$ 数组即可。

完整代码

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
template <typename T>
void read(T &x)
{
    x = 0;
    int f = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            f = -f;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y)
{
    read(x);
    read(y...);
}
typedef pair<int, int> pii;
pii E[100020];
int n, m;
vector<int> a[100020];
int dep[100020];
int fa[100020][20];
int S[100020]; // mask
int f[1 << 20];
map<pii, int> mp;
void dfs(int u, int p)
{
    dep[u] = dep[p] + 1;
    fa[u][0] = p;
    for (int i = 1; 1 << i <= dep[u]; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int v : a[u])
        if (v ^ p)
            dfs(v, u);
}
int LCA(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[fa[x][i]] >= dep[y])
            x = fa[x][i];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--)
        if (fa[x][i] ^ fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
void solve()
{
    read(n);
    for (int i = 1; i <= n; i++)
    {
        a[i].clear(), S[i] = dep[i] = 0;
        for (int j = 0; j < 20; j++)
            fa[i][j] = 0;
    }

    mp.clear();
    for (int i = 1; i < n; i++)
    {
        int u, v;
        read(u, v);
        E[i] = {u, v};
        a[u].push_back(v);
        a[v].push_back(u);
        mp[{u, v}] = mp[{v, u}] = i;
    }
    dfs(1, 0);
    read(m);
    for (int i = 0; i < m; i++)
    {
        int cnt = 1 << i;
        int u, v;
        read(u, v);
        int lca = LCA(u, v);
        for (int j = u; j != lca; j = fa[j][0])
            S[mp[{j, fa[j][0]}]] |= cnt;
        for (int j = v; j != lca; j = fa[j][0])
            S[mp[{j, fa[j][0]}]] |= cnt;
    }
    for (int i = 0; i < 1 << m; i++)
        f[i] = inf;
    set<int> s;
    for (int i = 1; i < n; i++)
        s.insert(S[i]);
    for (int i : s)
        f[i] = 1;
    // for (int i : s)
    //     cout << i << " ";
    // cout << endl;
    f[0] = 0;
    for (int i = 0; i < 1 << m; i++)
        for (int j : s)
            chkmn(f[i | j], f[i] + 1);
    cout << f[(1 << m) - 1] << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}