ovoo.cc

#include #include #include

using namespace std;

typedef long long dint; #define _l (long long int)

typedef pair <dint, int> dpr;

struct node { int v, t, sz; node* ch[2]; }; struct edge { int t, v; edge *next; };

const int maxn = 100009; const int maxh = 200009; const int maxnd = maxn * 43; const int mod = (1 « 23) * 7 * 17 + 1;

edge ebuf_arr[maxn], *ebuf(ebuf_arr), *head[maxn]; node nbuf_arr[maxnd], *nbuf(nbuf_arr), *nrt[maxn], *srt[maxn]; int n, k, ts, th; dint sans[maxn]; dpr hp[maxh];

#define szof(p) ((p)?(p->sz):0) inline void update(node* p) { p-> sz = szof(p-> ch[0]) + szof(p-> ch[1]) + 1; if (szof(p-> ch[0]) < szof(p-> ch[1])) swap(p-> ch[0], p-> ch[1]); }

inline node* allocNode(int v, int t) { node* np(nbuf ++); np-> v = v; np-> t = t; np-> ch[0] = np-> ch[1] = 0; np-> sz = 1; return np; }

node* hMerge(node* p, node* q) { if (!p || !q) { if (!p) return q; else return p; } else if (p-> v < q-> v) { p-> ch[1] = hMerge(p-> ch[1], q); update(p); return p; } else { q-> ch[1] = hMerge(q-> ch[1], p); update(q); return q; } } node* prMerge(node* p, node* q) { node* r; if (!p || !q) { if (!p) r = q; else r = p; } else if (p-> v < q-> v) { r = nbuf ++; memcpy(r, p, sizeof(node)); r-> ch[1] = prMerge(r-> ch[1], q); } else { r = nbuf ++; memcpy(r, q, sizeof(node)); r-> ch[1] = prMerge(r-> ch[1], p); } if (r) update(r); return r; }

dint sov() { while (ts < k && th) { dpr g(hp[0]); pop_heap(hp, hp + th –); int po(g. second), t; ++ ts; sans[ts] = -g. first; t = srt[po]-> t; srt[po] = prMerge(srt[po]-> ch[0], srt[po]-> ch[1]); if (srt[po]) { hp[th] = dpr(-sans[po] - srt[po]-> v, po); push_heap(hp, hp + ++ th); } srt[ts] = prMerge(srt[po], nrt[t]); if (srt[ts]) { hp[th] = dpr(-sans[ts] - srt[ts]-> v, ts); push_heap(hp, hp + ++ th); } } return sans[ts]; }

int main() { #ifndef ONLINE_JUDGE //freopen(".in", “r”, stdin); #endif

scanf("%d%d", &n, &k);
memset(head, 0, sizeof(head));
for (int i = 2; i <= n; ++ i) {
	int f, v;
	scanf("%d%d", &f, &v);
	ebuf-> t = i;
	ebuf-> v = v;
	ebuf-> next = head[f];
	head[f] = ebuf ++;
}
for (int i = 1; i <= n; ++ i) {
	nrt[i] = 0;
	for (edge* e = head[i]; e; e = e-> next)
		nrt[i] = hMerge(nrt[i], allocNode(e-> v, e-> t));
}
ts = 1;
sans[ts] = 0;
srt[ts] = nrt[1];
if (n > 1) {
	hp[0] = dpr(-nrt[1]-> v, 1);
	th = 1;
}
else
	th = 0;
printf("%d\n", (int)(sov() % mod));

}

Comments