题意

略

分析

稍微yy一下可以感觉就是一个不同子树合并堆,然后考场上写了一发左偏树,以为100分美滋滋.然而发现自己傻逼了,两个堆一一对应合并后剩下的一坨直接一次合并进去就行了.然鹅我这个sb把所有元素pop一次再merge进去…然后就O(n2)O(n^2)O(n2) 60分滚粗了…

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

时间复杂度分析:

每个点只会被pop出去一次,pop的时候伴随了一次pop一次merge.
每一对父子关系merge了一次

所以时间复杂度是O(nlogn)O(nlogn)O(nlogn)的.

CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &res) {

    char ch; while(!isdigit(ch=getchar()));

    for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0');

}

const int MAXN = 200005;

int n, w[MAXN], fir[MAXN], to[MAXN], nxt[MAXN], cnt;

inline void add(int u, int v) { to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt; }

struct LT {

    int ls, rs, dis;

}t[MAXN];

inline int merge(int x, int y) {

    if(!x || !y) return x + y;

    if(w[x] < w[y]) swap(x, y);

    t[x].rs = merge(t[x].rs, y);

    if(t[t[x].rs].dis > t[t[x].ls].dis)

        swap(t[x].ls, t[x].rs);

    t[x].dis = t[t[x].rs].dis + 1;

    return x;

}

inline int pop(int x) {

    int l = t[x].ls, r = t[x].rs;

    t[x].dis = t[x].ls = t[x].rs = 0;

    return merge(l, r);

}

inline int dfs(int x) {

    int u = 0, tmp;

    t[x].dis = t[x].ls = t[x].rs = 0;

    for(int i = fir[x], v; i; i = nxt[i]) {

        v = dfs(to[i]);

        tmp = 0;

        while(u && v) {

            int tmp1 = u; u = pop(u);

            int tmp2 = v; v = pop(v);

            tmp = merge(tmp, w[tmp1] > w[tmp2] ? tmp1 : tmp2);

        }

        if(u) tmp = merge(tmp, u);//就是这里我 sb地 pop出来又 push进去

        if(v) tmp = merge(tmp, v);

        u = tmp;

    }

    return merge(u, x);

}

int main () {

    read(n);

    for(int i = 1; i <= n; ++i) read(w[i]);

    for(int i = 2, x; i <= n; ++i) read(x), add(x, i);

    t[0].dis = -1;

    int rt = dfs(1);

    LL ans = 0;

    while(rt) ans += w[rt], rt = pop(rt);

    printf("%lld\n", ans);

}

巴特西

BZOJ 5494: [2019省队联测]春节十二响 (左偏树可并堆)

题意

分析

CODE

最新文章

热门文章

巴特西

BZOJ 5494: [2019省队联测]春节十二响 (左偏树 可并堆)

题意

分析

CODE

最新文章

热门文章

BZOJ 5494: [2019省队联测]春节十二响 (左偏树可并堆)