题解 | 在树上游玩

感觉主要难点在于题意理解，其实就是图的遍历。把连通的标记节点视为一个连通块，每个连通块只需要染色一条边，总方案数为每个连通块相邻节点数的连乘，最小代价为连通块数量。

#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
const int maxn = 200005;
bool vis[maxn] ={false};
bool masked[maxn] = {false};
vector<int> G[maxn]; // 邻接表

// 统计v能到达的neighbor数量
void DFS(int v, int &cnt){
    if(vis[v]) return;
    vis[v] = true;
    for(int i=0; i<G[v].size(); i++){
        if(masked[G[v][i]] && vis[G[v][i]] == false){ // 若是标记节点继续深入搜索
            DFS(G[v][i], cnt);
        }else if(vis[G[v][i]] == false){ // 若是没有访问的邻居节点
            cnt++;
        }
    }
}

int main() {
    int n, k, u, v;
    cin >> n >> k;
    for(int i=0; i<k; i++){
        cin >> v;
        masked[v] = true;
    }
    for(int i=0; i<n-1; i++){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    LL ans = 1, cost = 0;
    for(int i=1; i<=n; i++){
        if(masked[i] && vis[i] == false){
            int cnt = 0;
            DFS(i, cnt);
            cost++; // 最小代价为标记节点连通块数量
            ans = (ans * cnt) % MOD; // 方案数为当前方案数乘上每个连通块的邻居节点数量
        }
    }
    cout << cost << ' ' << ans;
    return 0;
}
// 64 位输出请用 printf("%lld")