题解 | 在树上游玩

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int long long
unordered_map<int,int> mp1,mp2;   // mp1记录节点i的父节点j，mp2记录节点i的邻居白点数

int find(int x) {
    return mp1[x]==x?x:mp1[x]=find(mp1[x]);
}

// 快速乘
int mul(int a,int b) {
    a = a%(1000000007LL);
    b = b%(1000000007LL);
    int ans = 0;
    while (b) {
        if (b&1) {
            ans +=a;
            ans %= 1000000007LL;
        }
        b>>=1;
        a<<=1;
    }
    return ans;
}

signed main() {
    int n,k;
    cin >> n >> k;
    vector<int> a(k+1);
    for (int i=1;i<=k;++i) {
        cin >> a[i];
        mp1[a[i]] = a[i];
    }
    int u,v;
    for (int i=1;i<=n-1;++i) {
        cin >> u >> v;
        if (mp1.count(u) && mp1.count(v)) {
            if (find(u) != find(v)) {
                mp2[find(v)]+=mp2[find(u)];
                mp2.erase(find(u));
                mp1[find(u)] = v;
            }
        } else if (mp1.count(u)) {
            mp2[find(u)]++;
        } else if (mp1.count(v)) {
            mp2[find(v)]++;
        }
    }
    int ans = 1;
    for (auto&it:mp2) {
        // ans = mul(ans,it.second);
        ans = ans*(it.second%(1000000007LL))%(1000000007LL);
    }
    cout << mp2.size() << " " << ans << endl;
}