题意

就是给你一棵以1为根的有根树
然后现在有m个线段
第i个点段可以覆盖a到b的路径，有一个代价$w[i]$
保证b是a的父亲
问你最少多少代价可以覆盖所有树边

前言

完全没有思路啊。。
保证b是a的父亲，就是路径不会拐弯，但是我完全想不到有什么用
如果考虑DP，也DP不出来
于是就膜题解了。。。。
最好要复习一下这个题。。
这种带反悔的贪心不是很熟啊
以后还是要多多练习

题解

我们考虑，因为每一条边都要被覆盖
我们就一条一条考虑
对于第i条，我们要找的就是他的子树里面，任意一条可以覆盖到它父亲的边，那么就是我们想要的
怎么选？贪心啊！维护一个堆就可以了
但是这样的话，如果随便选，那么可能会有后效性啊
于是我们可以给予它一个反悔的机会
在我们选了一条边i的时候，我们可以把堆里面所有元素减去$w[i]$
这个打个标记就可以了
表示如果我们选择堆里面这些边，这个边就不用选了，就可以返回代价
当然，如果这条边如果已经不能覆盖到它的父亲了，那么就把他删掉了
这个的话，我们可以访问到它的时候看一下它是否已经不合法了就可以了

我们可以写一个可并堆来支持这些操作

CODE:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=300005;
LL n,m;
struct qq{LL x,y,last;}e[N*2];LL num,last[N];
void init (LL x,LL y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
LL top[N];
LL w[N];
LL d[N];
LL r[N],l[N];
LL lazy[N];
LL root[N];
void change (LL x,LL y){lazy[x]+=y;w[x]+=y;}
void push_down (LL x)
{if (l[x]!=0) change(l[x],lazy[x]);if (r[x]!=0) change(r[x],lazy[x]);lazy[x]=0;
}
LL Merge (LL x,LL y)
{if (x==0||y==0) return x^y;if (w[x]>w[y]) swap(x,y);//维护小根堆 push_down(x);r[x]=Merge(r[x],y);if (d[r[x]]>d[l[x]]) swap(l[x],r[x]);d[x]=d[r[x]]+1;return x;
}
LL ans=0;
bool vis[N];
void dfs (LL x,LL fa)
{for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==fa) continue;dfs(y,x);root[x]=Merge(root[x],root[y]);}if (x==1) return ;vis[x]=true;while (vis[top[root[x]]]){push_down(root[x]);root[x]=Merge(r[root[x]],l[root[x]]);}if (root[x]==0){printf("-1\n");exit(0);}ans=ans+w[root[x]];change(root[x],-w[root[x]]);
}
int main()
{memset(vis,false,sizeof(vis));num=0;memset(last,-1,sizeof(last));scanf("%I64d%I64d",&n,&m);for (LL u=1;u<n;u++){LL x,y;scanf("%I64d%I64d",&x,&y);init(x,y);init(y,x);}for (LL u=1;u<=m;u++){LL x;scanf("%I64d%I64d%I64d",&x,&top[u],&w[u]);root[x]=Merge(root[x],u);}dfs(1,0);printf("%I64d\n",ans);return 0;
}