Description：

给出一棵树和若干条直上直下的链，每条链有权值，用权值和尽量小的链覆盖树上所有的点 ，求这个权值和。

$1\leqslant n\leqslant 10^6$

Solution：

首先可以考虑设计一个 $O(n^2)$ 的 $DP$ ： $f[i][j]$ 表示以 $i$ 为根的子树向上延长的最高点深度为 $j$ 的最小花费，考虑怎么优化这个转移，我们可以每个点存一个以 $cost$ 为关键字的二元组 $(len,cost)$ 的堆来代表这个二维数组，我们用可并堆来实现这个堆，然后每个点事先存入所有以这个点为最低点的链，转移有两种，一是每个子树内的链只用来覆盖子树内，从当前这个点新起一个链上去，这个就是在子树的堆中查询最小值，然后给当前这个点还没有和子树合并过的堆上打一个整体加法标记，然后另一种就是从子树中选一个贡献上来，先预处理子树前缀后缀最小值的和，然后枚举每个子树作为伸上去的那条链的来源，然后给这棵子树的堆整体打一个加法标记并和当前这个点合并就完成转移了。

注意合法性，也就是说每个点选出的链最高点深度应比这个点深度小，这个可以像可删堆那样处理。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 1000010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

struct node

{

	int lc,rc,d,f,val,add,top;

	node(){lc = rc = f = val = add = top = 0;d = -1;}

}t[MAXN];

int ptr = 0;

int newnode(){return ++ptr;}

int find(int x)

{

	return (t[x].f == 0 ? x : t[x].f = find(t[x].f));

}

void pushdown(int rt)

{

	t[t[rt].lc].val += t[rt].add;t[t[rt].lc].add += t[rt].add;

	t[t[rt].rc].val += t[rt].add;t[t[rt].rc].add += t[rt].add;

	t[rt].add = 0;

	return;

}

int merge(int x,int y)

{

	if(x == 0 || y == 0)return x + y;

	if(t[x].val > t[y].val)swap(x,y);

	pushdown(x);

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

	if(t[x].rc != 0)t[t[x].rc].f = x;

	if(t[t[x].lc].d < t[t[x].rc].d)swap(t[x].lc,t[x].rc);

	if(t[x].rc == 0)t[x].d = 0;

	else t[x].d = t[t[x].rc].d + 1;

	return x;

}

int dep[MAXN];

void dfs1(int k,int fa)

{

	dep[k] = dep[fa] + 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		dfs1(e[i].to,k);

	}

	return;

}

int top(int k,int &rt)

{

	while(dep[t[rt].top] > dep[k])rt = merge(t[rt].lc,t[rt].rc);

	return t[rt].val;

}

int root[MAXN];

bool uncover = false;

void dfs(int k,int fa)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		dfs(e[i].to,k);

	}

	int sum = 0; 

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		sum += top(e[i].to,root[e[i].to]);

	}

	t[root[k]].add += sum;t[root[k]].val += sum;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		int sum_ = sum - top(e[i].to,root[e[i].to]);

		t[root[e[i].to]].add += sum_;t[root[e[i].to]].val += sum_;

		root[k] = merge(root[k],root[e[i].to]);

	}

	if(root[k] == 0)uncover = true;

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

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

	dfs1(1,0);

	int u,v,w;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&u,&v,&w);

		int k = newnode();

		t[k].top = u;t[k].val = w;root[v] = merge(root[v],k);

	}

	dfs(1,0);

	if(!uncover)cout << top(1,root[1]) << endl;

	else puts("-1");

	return 0;

}