题解 | 在树上游玩

#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    constexpr int MOD = 1e9 + 7;

    // construct
    int n, k; cin >> n >> k;
    vector<vector<int>> tree(n);
    vector<bool> marked(n);

    for (int i = 0; i != k; ++i) {
        int index; cin >> index; --index;
        marked[index] = true;
    }

    for (int i = 0; i != n - 1; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // dfs
    vector<bool> visited(n);
    auto dfs = [&](auto&& dfs, int node, int parent) -> int {
        visited[node] = true;
        int count = 0;
        for (int neighbor : tree[node]) {
            if (!marked[neighbor]) {
                ++count;
            } else if (neighbor != parent) {
                count += dfs(dfs, neighbor, node);
            }
        }
        return count;
    };

    int count = 0;
    uintmax_t ways = 1;
    for (int i = 0; i < marked.size(); ++i) {
        if (marked[i] && !visited[i]) {
            ++count;
            ways = (ways * dfs(dfs, i, -1)) % MOD;
        }
    }

    cout << count << ' ' << ways;
}
// 64 位输出请用 printf("%lld")