A Very Easy Graph Problem

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int max_n = 2e5 + 100;
const int mod = 1e9 + 7;
int n, m;
int used[max_n];
struct edge
{
    int u, v, cost;
}E[max_n];
vector<pii> G[max_n];
bool cmp(edge e1, edge e2) { return e1.cost < e2.cost; }
int father[max_n];
int color[max_n];
ll cnt0[max_n];
ll cnt1[max_n];

int par[max_n];
int rak[max_n];

void init() {
    for (int i = 0;i <= n;i++) {
        par[i] = i;rak[i] = 0;
        father[i] = -1;
        cnt0[i] = cnt1[i] = 0;
        G[i].clear();
    }
}

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
    x = find(x);y = find(y);
    if (x == y)return false;
    if (rak[x] > rak[y])
        par[y] = x;
    else if (rak[y] > rak[x])par[x] = y;
    else {
        par[y] = x;rak[x]++;
    }return true;
}

void kruskai() {
    fill(used, used + 1 + m,false);
    sort(E + 1, E + 1 + m, cmp);
    for (int i = 1;i <= m;i++) {
        int u = E[i].u;int v = E[i].v;
        if (same(u, v))continue;
        used[i] = true;
        merge(u, v);
        G[u].push_back({ v,E[i].cost });
        G[v].push_back({ u,E[i].cost });
    }
}


ll quickpow(ll a, ll b) {
    if (b < 0) return 0;
    ll ret = 1;
    a %= mod;
    while (b) {
        if (b & 1) ret = (ret * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}

void solve(int u) {
    cnt1[u] = color[u];
    cnt0[u] = !color[u];
    if (G[u].size() == 1 && G[u][0].first == father[u])
        return;
    for (int i = 0;i < G[u].size();i++) {
        int v = G[u][i].first;
        if (father[u] == v)continue;
        father[v] = u;
        solve(v);
        cnt1[u] += cnt1[v];
        cnt0[u] += cnt0[v];
    }
    return;
}

int main() {
    ios::sync_with_stdio(0);
    int t;cin >> t;
    while (t--) {
        cin >> n >> m;
        init();
        for (int i = 1;i <= n;i++)cin >> color[i];
        for (int i = 1;i <= m;i++) {
            cin >> E[i].u >> E[i].v;
            E[i].cost = i;
        }kruskai();
        int root = 1;
        solve(root);
        ll ans = 0;
        for (int i = 1;i <= m;i++) {
            if (!used[i])continue;
            int u = E[i].u;int v = E[i].v;
            if (father[v] == u)swap(u, v);
            ll cont = (cnt0[root] - cnt0[u]) * cnt1[u] + (cnt1[root] - cnt1[u]) * cnt0[u];
            ll res = (cont % mod) * (quickpow(2, E[i].cost) % mod) % mod;
            ans = (ans + res) % mod;
        }cout << ans << endl;
    }
}