图转树 最小生成树 树形dp2020 Multi-University Training Contest 6 A Very Easy Graph Problem
题目大意：
一张 m 大小的图，每一个节点被标记为0或者1，第 (i) 条边的大小是 (2^i) ，问是否任意两个01点对之间的最短路的距离和。
题解：
注意这个边的大小是 (2^i) ，对于 (2^i>2^1+2^2+2^3+...2^{i-1}) 所以优先考虑前面的边，如果前面的边可以保证联通，则前面的边一定更优，所以把这个图转化成一棵树，然后树形dp即可。
之前联想杯有一个类似的题目：https://acm.ecnu.edu.cn/contest/270/problem/D/
#include <bits/stdc++.h>
#define debug(x) cout<<"debug:"<<#x<<" = "<<x<<endl;
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
const int mod = 1e9+7;
int head[maxn],to[maxn<<1],nxt[maxn<<1],cnt,f[maxn],have[maxn],num,n,m,siz[maxn];
ll w[maxn<<1],p[maxn];
void Init(){
p[0] = 1;
for(int i=1;i<maxn;i++) p[i]=p[i-1]*2%mod;
}
void init(int n){
cnt = 0;
for(int i=0;i<=n;i++) head[i] = 0,f[i] = i,have[i] = 0;
}
void add(int u,int v,int i){
++cnt,to[cnt]=v,nxt[cnt]=head[u],w[cnt]=p[i],head[u]=cnt;
++cnt,to[cnt]=u,nxt[cnt]=head[v],w[cnt]=p[i],head[v]=cnt;
}
int Find(int x) {
return x == f[x] ? x : f[x] = Find(f[x]);
}
void unite(int x,int y){
x = Find(x);
y = Find(y);
if(x==y) return ;
f[x] = y;
}
bool same(int x,int y){
return Find(x)==Find(y);
}
ll dp[maxn];
void dfs(int u,int pre) {
// printf("u=%d pre=%d
",u,pre);
dp[u] = 0, siz[u] = 1;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v == pre) continue;
dfs(v, u);
have[u] += have[v];
siz[u] += siz[v];
ll blackIn = have[v], blackOut = num - blackIn;
ll whiteIn = siz[v] - have[v], whiteOut = n - num - whiteIn;
// printf("u=%d v=%d
",u,v);
dp[u] = ((dp[u] + dp[v]) % mod + (blackIn * whiteOut + whiteIn * blackOut) % mod * w[i] % mod) % mod;
}
}
int main() {
Init();
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
init(n),num = 0;
for(int i=1;i<=n;i++) scanf("%d",&have[i]),num += have[i];
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
if (same(u, v)) continue;
unite(u, v);
add(u, v, i);
}
dfs(1,0);
printf("%lld
",dp[1]);
}
return 0;
}