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

NO IMAGE

傳送門
題目: 就是同時有k個人從一顆有n個節點的樹的根節點出發, 走過的點都可以累加到ans中, 一個點只能被累加一次, 問最大能累加多少.

思路: 其實最開始做這道題是用的倒著做的, 然後dp了一下, 現在學了這個就用這個再做做, 實際上我們從葉子節點開始每次每個節點只加在價值最大的那個子節點上, 然後加完了,從根節點開始一個個刪掉, 取前k大即可.

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];
int cnt, head[maxn];
void init() {
cnt = 0; Fill(head, -1);
}
void add(int u, int v, int w) {
e[cnt] = node{v, head[u], w};
head[u] = cnt  ;
}
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);
add(u, v, 1); add(v, u, 1);
}
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) {
e[cnt] = node{v, head[u]};
head[u] = cnt  ;
}
int in[maxn], vis[maxn];
ll val[maxn], dp[maxn];
struct result {
ll road; int id;
bool operator < (const result& _) const {
return road > _.road;
}
}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);
add(v, u);
in[u]  ;
}
int idx = 0;
for (int i = 1 ; i <= n ; i   ) {
if (!in[i]) {
b[  idx].id = i;
b[idx].road = dfs1(i);
}
}
sort(b 1, b 1 idx);
for (int i = 1 ; i <= idx ; i   ) {
sum = 0; dfs2(b[i].id);
b[i].road = sum;
}
sort(b 1, b 1 idx);
ll ans = 0;
for (int i = 1 ; i <= min(idx, k) ; i   ) {
ans  = b[i].road;
}
printf("Case #%d: %lld\n", cas  , ans);
}