Contest Hunter - OVOO

題意：

給出一顆有根樹，每次可以從樹上取包括根節點的一個連通塊；

定義連通塊的權值為塊内邊的權值之和；

詢問第k小的連通塊的權值是多少；

n<=100000，k<=100000；

此題為CH弱省胡策#1T3；

題解：

PoPoQQQ大爺好神！

這道題也是利用A*搜尋來求K大值，但是狀态比較難以表示；

先考慮怎麼搜尋，對于一個已經選完了的點集，下一次可能再選的點有哪些？

可能是上一次選的點的兒子，也可能是回溯到上一層，選比上一層選的點大的下一個點；

注意第二個可能性，這個是維護了一個有序性，保證方案權值遞增并且不會出現重複方案；

這是一個A*的過程，我說的似乎不太好了解。。

每一種狀态加入優先隊列來跑A*；

貼個圖來示範一下：

是以每次是将這些邊集中最小的邊拿出來，那就要用到一個堆；

而如果對于每個狀态搞一個堆妥妥MLE；

那就用可持久化左偏樹來搞(可持久化資料結構get√)；

這樣空間複雜度是O((n+k)logn)的(大概)；

當然，将一個結點的所有兒子加入堆不能暴力，對每個結點維護一個兒子可并堆就好了；

代碼：

#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 110000
#define pr pair<ll,heap*>
using namespace std;
typedef long long ll;
struct heap
{
	heap *l, *r;
	int dis, no, val;
	heap();
}*null = new heap(), *root[N];
priority_queue<pr,vector<pr> ,greater<pr> >q;
heap::heap()
{
	l = null, r = null;
	dis = 0;
}
heap* Insert(heap *x, heap *y)
{
	if (x == null || y == null)
		return x == null ? y : x;
	if (x->val > y->val)
		swap(x, y);
	x->r = Insert(x->r, y);
	if (x->l->dis < x->r->dis)
		swap(x->l, x->r);
	x->dis = x->r->dis + 1;
	return x;
}
heap* merge(heap *x, heap *y)
{
	if (x == null || y == null)
		return x == null ? y : x;
	if (x->val > y->val)
		swap(x, y);
	heap *p = new heap();
	*p = *x;
	p->r = merge(p->r, y);
	if (p->l->dis < p->r->dis)
		swap(p->l, p->r);
	p->dis = p->r->dis + 1;
	return p;
}
int main()
{
	int n, m, i, j, k, x, y, v;
	ll ans;
	heap *p;
	null->l = null->r = null;
	null->no = null->val = 0;
	scanf("%d%d",&n,&k);
	for (i = 1; i <= n; i++)		root[i] = null;
	for (i = 1; i < n; i++)
	{
		scanf("%d%d", &x, &v);
		p = new heap();
		p->no = i+1, p->val = v;
		root[x]=Insert(root[x], p);
	}
	p = new heap();
	p->no = 1, p->val = 0;
	q.push(pr(0, p));
	for (i = 1, ans = 0; i <= k&&!q.empty(); i++)
	{
		pr now = q.top();
		q.pop();
		ans = now.first;
		p = now.second;
		x = p->no;
		v = p->val;
		p = merge(p->l, p->r);
		if(p!=null)
			q.push(pr(now.first - v + p->val, p));
		p = merge(p, root[x]);
		if(p!=null)
			q.push(pr(now.first + p->val, p));
	}
	printf("%d\n", ans % 998244353);
}