1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
| #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x = 0, f = 1; char c = getchar(); while (c > '9' || c < '0') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + c - '0'; c = getchar(); } return x * f; } const int N = 2E5 + 10; int n; int w[N];
int head[N], to[N << 1], nxt[N << 1], ecnt; void adde(int a, int b) { ecnt++; nxt[ecnt] = head[a]; head[a] = ecnt; to[ecnt] = b; }
int f[N]; int findf(int x) { return f[x] == 0 ? x : f[x] = findf(f[x]); }
int leaves[N], id; bool selected[N]; struct edge { int from, to, w, v; } es[N << 1]; int necnt; void inse(int a, int b, int w, int v) { necnt++; es[necnt] = {a, b, w, v}; } void kruskal() { sort(es + 1, es + 1 + necnt, [](const edge &a, const edge &b) { return a.w < b.w; }); int l = 1; int k = 0; int mst = 0; while (l <= n) { int r; for (r = l; r <= n; r++) { if (es[r].w != es[r + 1].w) break; } for (int i = l; i <= r; i++) { if (findf(es[i].from) != findf(es[i].to)) { selected[es[i].v] = 1; k++; } } for (int i = l; i <= r; i++) { int fu = findf(es[i].from); int fv = findf(es[i].to); if (fu == fv) continue; mst += es[i].w; f[fu] = fv; } l = r + 1; } cout << mst << ' ' << k << endl; for (int i = 1; i <= n; i++) { if (selected[i]) cout << i << ' '; } cout << endl; } void dfs1(int x, int fa) { bool vis = 0; for (int i = head[x]; i; i = nxt[i]) { int v = to[i]; if (v != fa) { dfs1(v, x); vis = 1; leaves[x] += leaves[v]; } } if (!vis) { id++; leaves[x] = 1; } } void dfs2(int x, int fa, int l) {
inse(l, l + leaves[x], w[x], x); for (int i = head[x]; i; i = nxt[i]) { int v = to[i]; if (v != fa) { dfs2(v, x, l); l += leaves[v]; } } } signed main() { n = read(); for (int i = 1; i <= n; i++) { cin >> w[i]; } for (int i = 1; i < n; i++) { int a = read(), b = read(); adde(a, b); adde(b, a); } dfs1(1, 0); dfs2(1, 0, 1); kruskal(); return 0; }
C++
|