(6832 A Very Easy Graph Problem)
题意
给定一张 (n) 个顶点，(m) 条边的无向图，输入的第 (i) 条边的权值为 (2^i)
对于每一个顶点，标记为 (0) 或 (1)
请计算
[sum_{i = 1}^{n}sum_{j = 1}^ndis(i, j) imes left[a_{i} = 1wedge a_{j} = 0
ight]
]
其中 (dis(i, j)) 表示 (i) 到 (j) 的最短路
且 (left[a_{i} = 1wedge a_{j} = 0 ight]) 为 (Iverson bracket)，即条件成立取值为 (1)，不成立取值为 (0)
(1leq nleq 10^5, 1leq mleq 2 imes 10^5)，对答案取模 (10^9 + 7)
题解
题意等价于，计算所有 (1) 点到所有 (0) 点的最短路之和
注意到边权的特殊性，即 (2^i > 2^1 + 2^2 + ... + 2^{i - 1})
设当前输入边 (i)，端点为 (u, v)
- 若 (u, v) 已联通，那么必然有 (dis(u, v) < 2^i)
- 若 (u, v) 未联通，那么必然有 (dis(u, v) = 2^i)
所以考虑，对所有边按输入顺序构造 (MST)，模拟 (Kruskal) 算法，得到一颗生成树
由前面的证明知道，这颗生成树的特殊之处在于
- 是一颗最小生成树
- 树上任意两点的距离一定是最短路径
下面在新的树上作树形 (dp)，记录节点所在子树的 (0) 点和 (1) 点的数量，枚举树上每一条边计算贡献即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define dbg(a, l, r) for(int i = l; i <= r; ++i) printf("%lld%c", a[i], "
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int N = 2e5 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
int T, n, m, zero, one, a[N], pre[N], rk[N], dp[N][2];
vector<pii> g[N];
pii E[N];
void ini(int n) {for(int i = 1; i <= n; ++i) pre[i] = i, rk[i] = 1;}
int findPre(int x) {return pre[x] == x ? x : pre[x] = findPre(pre[x]);}
void uni(int x, int y)
{
int fx = findPre(x), fy = findPre(y);
if(fx == fy) return;
if(rk[fx] < rk[fy]) pre[fx] = fy, rk[fy] += rk[fx];
else pre[fy] = fx, rk[fx] += rk[fy];
}
bool commonpre(int x, int y) {int fx = findPre(x), fy = findPre(y); return fx == fy;}
void debug()
{
for(int i = 1; i <= n; ++i) {
cout << i << ":" << endl;
for(auto it: g[i]) cout << it.fi << ' ';
cout << endl;
}
for(int i = 1; i <= n; ++i) {
cout << i << ":" << endl;
cout << "0's num: " << dp[i][0] << endl;
cout << "1's num: " << dp[i][1] << endl;
}
}
void dfs(int u, int v, LL &ans)
{
dp[u][a[u]]++;
for(auto i: g[u]) {
if(i.fi != v) {
dfs(i.fi, u, ans);
dp[u][0] += dp[i.fi][0];
dp[u][1] += dp[i.fi][1];
}
}
for(auto i: g[u]) {
if(i.fi != v) {
LL res1 = dp[i.fi][0] * (one - dp[i.fi][1]) % MOD * i.se % MOD;
LL res2 = dp[i.fi][1] * (zero - dp[i.fi][0]) % MOD * i.se % MOD;
ans = (ans + res1 + res2) % MOD;
}
}
}
int main()
{
scanf("%d", &T);
while(T--) {
scanf("%d %d", &n, &m);
memset(dp, 0, sizeof(dp));
zero = one = 0;
for(int i = 0; i <= n; ++i) g[i].clear();
ini(n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
if(a[i] == 0) zero++;
else one++;
}
for(int i = 1; i <= m; ++i) {
int u, v;
scanf("%d %d", &u, &v);
E[i] = pii(u, v);
}
int cnt = 0;
LL tp = 1, ans = 0;
for(int i = 1; i <= m; ++i) {
int x = E[i].fi, y = E[i].se;
tp *= 2, tp %= MOD;
if(!commonpre(x, y)) {
uni(x, y);
g[x].pb(pii(y, tp));
g[y].pb(pii(x, tp));
if(cnt == n - 1) break;
}
}
dfs(1, -1, ans);
//debug();
printf("%lld
", ans);
}
return 0;
}
/*
3
3 2
0 1 0
3 1
3 2
3 2
1 1 0
3 1
3 2
4 4
1 0 1 0
1 2
2 3
3 4
1 4
*/