25暑期5

Problem K

给 \(n\) 个节点的一棵树，上面有 \(m\) 个特殊边。有 \(k\) 个路径（从某点到某点），选出最少数量的路径包含所有的 \(m\) 条特殊边。无解输出 -1；有解还要求方案数。

\(2≤n≤2×10^5, 1\leq m\leq 22, 1\leq k\leq 2\times 10^5\)。

点击查看题解

特殊边较少，设第 \(i\) 条特殊边边权为 \(2^i\)。可求 \(k\) 个路径上的边权状态（只需利用树上前缀或，直接取路径两端前缀和的异或即可）。断言边权和不同的路径数量较少（设有 \(k\) 种），设 \(f(i)\) 表示边权状态为 \(i\)（状压）时所需最少路径数量，类似背包，可同时求方案数。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
const int N = 200005, M = 25, O = 4500005, mod = 998244353, inf = 1145141919810;
vector<PII > e[N * 2];
vector<int> val;
int n, m, k, spe[N], a[N];
int f[O], g[O], num[O];
int ans1 = -1, ans2;

void init(int now,int dad) {
    for (PII i: e[now]) {
        int to = i.first, v = spe[i.second];
        if (to == dad)
            continue;
        a[to] = (a[now] | v);
        init(to, now);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int u, v;
    cin >> n >> m >> k;
    for (int i = 1; i <= n - 1; i++) {
        cin >> u >> v;
        e[u].push_back({v, i});
        e[v].push_back({u, i});
    }
    for (int i = 1; i <= m; i++) {
        cin >> u;
        spe[u] = (1ll << (i - 1));
    }
    a[1] = 0;
    init(1, 1);
    val.push_back(0);
    for (int i = 1; i <= k; i++) {
        cin >> u >> v;
        int tmp = (a[u] ^ a[v]);
        if (num[tmp] == 0) {
            val.push_back(tmp);
        }
        num[tmp]++;
    }
    g[0] = 1;
    k = val.size() - 1;
    for (int i = 1; i <= ((1ll << m) - 1); i++)
        f[i] = inf;
    for (int i = 1; i <= k; i++) {
        for (int j = ((1ll << m) - 1); j >= 0; j--) {
            if (f[j | val[i]] > f[j] + 1) {
                f[j | val[i]] = f[j] + 1;
                g[j | val[i]] = g[j] * num[val[i]] % mod;
            } else if (f[j | val[i]] == f[j] + 1) {
                g[j | val[i]] = (g[j | val[i]] + g[j] * num[val[i]]) % mod;
            }
        }
    }
    if (f[(1ll << m) - 1] >= inf)
        cout << "-1" << endl;
    else {
        ans1 = f[(1ll << m) - 1];
        ans2 = g[(1ll << m) - 1];
        cout << ans1 << " " << ans2 << endl;
    }
    return 0;
}