左偏树又叫做可合并堆，比较容易理解，也比较好写。。
它并不是真正的堆，虽然是二叉树，但并不是完全二叉树，也并不平衡。
核心操作在于将两颗左偏树合并为一颗左偏树。
首先确定维护的是集合的最大值还是最小值。
然后就是随便搞搞。。。
推荐05年集训队论文，很简单易懂。
目前还没有掌握删除左偏树中任意指定节点的方法。。。
【BZOJ2809】
就是求出一个节点，选出以其为根的子树中自己之外的一些点，使他们的花费和不超过给定值，定义这个节点的贡献值为他的领导力与选出的点的最大个数，求出所有节点贡献值的最大值。
由底至上进行统计，维护大根可合并堆，并记录当前左偏树的花费和以及点的总数,对于当前节点，首先贪心地把全部子节点加入左偏树中，再不断删除根，直到花费和不超过给定值。此时更新答案。
【代码】
#include<cstdio>
#include<cstring>
#include<cctype>
#define N (100010)
typedef long long LL;
inline LL max(LL a , LL b)
{
return a > b ? a : b;
}
inline char getc()
{
static const int L = 1 << 15;
static char buf[L] , *S = buf , *T = buf;
if (S == T)
{
T = (S = buf) + fread(buf , 1 , L , stdin);
if (S == T)
return EOF;
}
return *S++;
}
inline int getint()
{
static char c;
while(!isdigit(c = getc()));
int tmp = c - '0';
while(isdigit(c = getc()))
tmp = (tmp << 1) + (tmp << 3) + c - '0';
return tmp;
}
int weigh[N] , root[N] , cost[N] , size[N] , d[N] , l[N] , r[N];
LL addcost[N];
inline void swap(int &x , int &y)
{
int tmp = x;
x = y;
y = tmp;
}
inline int merge(int x , int y)
{
if (!x || !y)
return x + y;
if (cost[x] < cost[y])
swap(x , y);
r[x] = merge(r[x] , y);
if (d[l[x]] < d[r[x]])
swap(l[x] , r[x]);
d[x] = d[r[x]] + 1;
return x;
}
int head[N] , next[N];
int main()
{
int n , M;
n = getint();
M = getint();
register int i , j , k;
int pa;
for(i = 1 ; i <= n ; ++i)
{
size[i] = 1;
pa = getint();
root[i] = i;
next[i] = head[pa];
head[pa] = i;
cost[i] = getint();
addcost[i] = cost[i];
weigh[i] = getint();
}
LL ans = 0;
for(i = n ; i ; --i)
{
for(j = head[i] ; j ; j = next[j])
{
addcost[i] += addcost[j];
size[i] += size[j];
root[i] = merge(root[i] , root[j]);
}
while(addcost[i] > M)
{
addcost[i] -= cost[root[i]];
--size[i];
root[i] = merge(l[root[i]] , r[root[i]]);
}
ans = max(ans , (LL)size[i] * weigh[i]);
}
printf("%lld" , ans);
return 0;
}
【BZOJ1455】
利用并查集维护当前节点所在左偏树的根。
此外，删除最小根时，只需进行将根的root指向根的左右子树合并后的根，再令根的root的root指向根的root。
【代码】
#include<cstdio>
#include<cstring>
#include<cctype>
inline char getc()
{
static const int L = 1 << 15;
static char buf[L] , *S = buf , *T = buf;
if (S == T)
{
T = (S = buf) + fread(buf , 1 , L , stdin);
if (S == T)
return EOF;
}
return *S++;
}
inline int getint()
{
static char c;
while(!isdigit(c = getc()));
int tmp = c - '0';
while(isdigit(c = getc()))
tmp = (tmp << 1) + (tmp << 3) + c - '0';
return tmp;
}
inline char getch()
{
static char c;
while((c = getc()) != 'K' && c != 'M');
return c;
}
#define N (1000010)
inline void swap(int &x , int &y)
{
int tmp = x;
x = y;
y = tmp;
}
int weigh[N] , root[N] , l[N] , r[N] , d[N];
int find(int x)
{
if (x == root[x])
return x;
root[x] = find(root[x]);
return root[x];
}
int merge(int x , int y)
{
if (!x || !y)
return x + y;
if (weigh[x] > weigh[y])
swap(x , y);
r[x] = merge(r[x] , y);
if (d[l[x]] < d[r[x]])
swap(l[x] , r[x]);
d[x] = d[r[x]] + 1;
return x;
}
bool exist[N];
int main()
{
int n = getint();
register int i , j , k;
for(i = 1 ; i <= n ; ++i)
{
weigh[i] = getint();
root[i] = i;
exist[i] = 1;
}
int ask = getint();
while(ask--)
{
char sign = getch();
if (sign == 'K')
{
int a = getint();
if (!exist[a])
{
puts("0");
continue;
}
else
{
int tmproot = find(a);
printf("%d\n" , weigh[tmproot]);
exist[tmproot] = 0;
root[tmproot] = merge(l[tmproot] , r[tmproot]);
root[root[tmproot]] = root[tmproot];
}
}
else
{
int a = getint();
int b = getint();
if (!exist[a] || !exist[b])
continue;
int tmpa = find(a);
int tmpb = find(b);
if (tmpa == tmpb)
continue;
root[tmpa] = root[tmpb] = merge(tmpa , tmpb);
}
}
return 0;
}
