https://www.luogu.com.cn/problem/CF1515F
首先必须保证 s u m a [ i ] ≥ ( n − 1 ) ∗ x suma[i]\ge (n-1)*x suma[i]≥(n−1)∗x
可以证明是充要的
考虑随便拉一棵树出来,从叶子结点考虑,如果
a
[
u
]
≥
x
a[u]\ge x
a[u]≥x,那么把
u
u
u和父亲合并,否则先不管
u
u
u,把
u
u
u删了,剩下的又是一个子问题,然后最后再把子问题得到的那个点和
u
u
u合并
code:
#include<bits/stdc++.h>
#define N 300050
#define ll long long
using namespace std;
struct edge {
int v, nxt, c;
} e[N << 1];
int p[N], eid;
void init() {
memset(p, -1, sizeof p);
eid = 0;
}
void insert(int u, int v, int c) { //printf("%d --> %d %d\n", u, v, c);
e[eid].v = v;
e[eid].nxt = p[u];
e[eid].c = c;
p[u] = eid ++;
}
int fa[N];
int get(int x) {
return fa[x] == x? x : (fa[x] = get(fa[x]));
}
int l, r, n, m, K, ans[N];
ll a[N];
void dfs(int u, int fa, int id) {
for(int i = p[u]; i + 1; i = e[i].nxt) {
int v = e[i].v, c = e[i].c;
if(v == fa) continue;
// printf("%d --> %d %d\n", u, v, c);
dfs(v, u, c);
}
// printf(" %d %d %d %d\n", u, a[u], l, r);
if(u == 1) return ;
if(a[u] >= K) a[fa] += a[u] - K, ans[l ++] = id;
else ans[r --] = id;
}
int main() {
init();
scanf("%d%d%d", &n, &m, &K);
ll s = 0;
for(int i = 1; i <= n; i ++) fa[i] = i, scanf("%lld", &a[i]), s += a[i];
if(s < 1ll * (n - 1) * K) {
printf("NO");
return 0;
}
for(int i = 1; i <= m; i ++) {
int x, y;
scanf("%d%d", &x, &y);
if(get(x) == get(y)) continue;
insert(x, y, i), insert(y, x, i);
fa[get(x)] = get(y);
}
l = 1, r = n - 1;
dfs(1, 1, 0);
//printf(" %d %d\n", l, r);
printf("YES\n");
for(int i = 1; i < n; i ++) printf("%d\n", ans[i]);
return 0;
}