大锑问题之
1.树上问题,先将子树答案更新后,用新的值更新答案
//可并堆合并
struct MHN{ ll val, lc, rc, sz, dist, sum;} H[100007];
int merge(int x, int y)
{
if((!x) || (!y)) return x | y;
if(H[x].val < H[y].val) swap(x, y);
H[x].sz += H[y].sz;//H[y]会改掉,应该先加完再合并, 100pts
H[x].sum += H[y].sum;
H[x].rc = merge(H[x].rc, y);
if(H[H[x].lc].dist < H[H[x].rc].dist) swap(H[x].lc, H[x].rc);
H[x].dist = H[H[x].rc].dist + 1;
// H[x].sz += H[y].sz;//H[y]被改掉, 8pts
// H[x].sum += H[y].sum;
// 也可以写成这样:
// H[x].sz = H[H[x].lc].sz + H[H[x].rc].sz + 1;
// H[x].sum = H[H[x].lc].sum + H[H[x].rc].sum + H[x].val;
return x;
}