# bzoj – 3252 攻略 【思維 or 可並堆】 好題

AC Code

``````const int maxn = 2e5   5;
int root[maxn];
struct Ltree {
int ls[maxn], rs[maxn];
ll val[maxn];
int Un(int x, int y){
if (!x || !y) return x y;
if (val[x] < val[y]) swap(x,y);
rs[x] = Un(rs[x], y);
swap(ls[x], rs[x]);
return x;
}
void pop(int &x) {
x = Un(ls[x], rs[x]);
}
int top(int x) {
return val[x];
}
}heap;
ll a[maxn];
int n, m;
struct node {
int to, next, w;
}e[maxn<<1];
void init() {
}
void add(int u, int v, int w) {
}
void dfs(int u, int fa) {
for (int i = head[u] ; ~i ; i = e[i].next) {
int to = e[i].to;
if (to == fa) continue;
dfs(to, u);
root[u] = heap.Un(root[u], root[to]);
}
heap.val[root[u]]  = a[u];
}
void solve() {
scanf("%d%d", &n, &m); init();
for (int i = 1 ; i <= n ; i   ) {
scanf("%lld", a i);
root[i] = i;
}
for (int i = 2 ; i <= n ; i   ) {
int u, v; scanf("%d%d", &u, &v);
}
dfs(1, -1);
ll ans = 0;
while(m--) {
ans  = heap.val[root[1]];
heap.pop(root[1]);
if (!root[1]) break;
}
printf("%lld\n", ans);
}``````

``````struct node {
int to, next;
}e[maxn];
int cnt, head[maxn], cas = 1;
int n, k;
void add(int u, int v) {
}
int in[maxn], vis[maxn];
ll val[maxn], dp[maxn];
struct result {
bool operator < (const result& _) const {
}
}b[maxn];
void init() {
cnt = 0; Fill(head, -1); Fill(dp, -1);
Fill(in, 0); Fill(vis, 0); Fill(b, 0);
}
ll dfs1(int u) {
if (dp[u] != -1) return dp[u];
ll sum = val[u];
for (int i = head[u] ; ~i ; i = e[i].next) {
int to = e[i].to;
sum  = dfs1(to);
}
return dp[u] = sum;
}
ll sum;
void dfs2(int u) {
if (vis[u]) return ;
vis[u] = 1;
sum  = val[u];
for (int i = head[u] ; ~i ; i = e[i].next) {
int to = e[i].to;
dfs2(to);
}
}
void solve()
{
scanf("%d%d", &n, &k);
for (int i = 1 ; i <= n ; i   ) {
scanf("%d", val i);
}
init();
for (int i = 1 ; i <= n-1 ; i   ) {
int u, v;
scanf("%d%d", &u, &v);
in[u]  ;
}
int idx = 0;
for (int i = 1 ; i <= n ; i   ) {
if (!in[i]) {
b[  idx].id = i;
}
}
sort(b 1, b 1 idx);
for (int i = 1 ; i <= idx ; i   ) {
sum = 0; dfs2(b[i].id);