【题意】给定n个点的树，m条从下往上的链，每条链代价ci，求最少代价使得链覆盖所有边。n,m<=3*10^5，ci<=10^9，time=4s。
【算法】树形DP+线段树||可并堆
【题解】从每条边都需要一条链来覆盖的角度出发，令f[i]表示覆盖子树 i 以及 i到fa[i]的边（i->fa[i]）的最小代价，整个过程通过dfs从下往上做。
由于f[son[i]]已知，所以f[i]的转移实际上是考虑覆盖i->fa[i]的链，定义这条链为主链。那么f[i]=min(c+Σf[k])，c是主链代价，k是主链上在i子树内的所有点的子节点（不含主链上点），所有起点在子树i内终点在i的祖先的链都可以作为主链，取最小值。
自然地，可以在递归的过程中将Σf[k]并入c中。具体而言，对于每个点x：
1.删。将终点在x的链删除。
2.加。记sum=Σf[son[i]]，son[i]子树内所有的链c+=sum-f[son[i]]（就是把Σf[k]并入c中），特别地，起点在i的链c+=sum。
3.取。f[i]是子树i中所有的链c的最小值。
现在需要快速支持子树加值和子树求最小值的操作，可以用线段树按dfs序维护所有链实现（把链按起点的dfs序作为线段树下标）。
复杂度O(n log n)。
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
const int maxn=;
const ll inf=1e15;
struct tree{int l,r;ll delta,mins;}t[maxn*];
struct edge{int v,from;}e[maxn*];
vector<int>v[maxn];
int n,m,ku[maxn],kv[maxn],kw[maxn],kp[maxn],tot=,dfsnum=,first[maxn],be[maxn],ed[maxn];
ll a[maxn],f[maxn];
void ins(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
void dfs_order(int x,int fa){
be[x]=dfsnum+;
for(int i=;i<(int)v[x].size();i++){
kp[v[x][i]]=++dfsnum;
a[dfsnum]=kw[v[x][i]];
}
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){
dfs_order(e[i].v,x);
}
ed[x]=dfsnum;
if(be[x]>ed[x]){printf("-1");exit();}
}
void modify(int k,ll x){t[k].mins+=x;t[k].delta+=x;}
void up(int k){t[k].mins=min(t[k<<].mins,t[k<<|].mins);}
void down(int k){
if(t[k].delta){
modify(k<<,t[k].delta);
modify(k<<|,t[k].delta);
t[k].delta=;
}
}
void build(int k,int l,int r){
t[k].l=l;t[k].r=r;t[k].delta=;
if(l==r){t[k].mins=a[l];}else{
int mid=(l+r)>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
up(k);
}
}
void add(int k,int l,int r,ll x){
if(l<=t[k].l&&t[k].r<=r){modify(k,x);return;}
down(k);
int mid=(t[k].l+t[k].r)>>;
if(l<=mid)add(k<<,l,r,x);
if(r>mid)add(k<<|,l,r,x);
up(k);
}
ll ask(int k,int l,int r){
if(l<=t[k].l&&t[k].r<=r){return t[k].mins;}
down(k);
int mid=(t[k].l+t[k].r)>>;
ll ans=inf;
if(l<=mid)ans=ask(k<<,l,r);
if(r>mid)ans=min(ans,ask(k<<|,l,r));
return ans;
}
ll dp(int x,int fa){
f[x]=;ll sum=;
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa)sum+=dp(e[i].v,x);
for(int i=;i<(int)v[x].size();i++)add(,v[x][i],v[x][i],inf);
add(,be[x],ed[x],sum);
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){
add(,be[e[i].v],ed[e[i].v],-f[e[i].v]);
}
f[x]=ask(,be[x],ed[x]);
if(x!=&&f[x]>=inf){printf("-1");exit();}
return f[x];
}
int main(){
n=read();m=read();
for(int i=;i<n;i++){
int u=read(),v=read();
ins(u,v);ins(v,u);
}
for(int i=;i<=m;i++){
ku[i]=read(),kv[i]=read(),kw[i]=read();
v[ku[i]].push_back(i);
}
dfsnum=;
dfs_order(,);
build(,,dfsnum);
for(int i=;i<=m;i++)v[ku[i]].clear();
for(int i=;i<=m;i++)v[kv[i]].push_back(kp[i]);
dp(,);
ll ans=;
for(int i=first[];i;i=e[i].from)ans+=f[e[i].v];
printf("%lld",ans);
return ;
}
可并堆写法：
核心思想仍是——每条边都需要一条链来覆盖。
整个过程通过dfs从下往上做，对于每个点x，维护一个堆包含所有起点在子树x内终点为x的祖先的链（按价值从小到大）。
维护的过程只需要将所有儿子的堆合并过来，然后删除终点在x的链。（堆的删除不需要真的删除，只需要在调用堆顶是判断是否已被删除）
接下来考虑选用哪些链，考虑点x时，子树x内所有边都已经被覆盖，所以实际上是在考虑x->fa[x]这条边的覆盖，那么此时堆x中的链都可以随意选用，但是选用哪条对未来更优当前并不知道。
采用反悔的思想，先选用代价w最小的链，并将堆整体标记-w，之后考虑选用其它边实际上就是“更换”的操作了，当然选用的代价w的链不移除（在堆中代价为0）将一直发挥作用直至其终点。
这样做的正确性就在于，在标记-w时，堆中所有的链可以随意换用，因为都会影响x->fa[x]而子树x已经完全覆盖了无须考虑。
总结起来，对于点x：
1.合并所有son[x]。
2.找到堆顶w加入答案。（不需要特别做删除）
3.整体标记-w。
复杂度O(n log n)，常数优势明显。
#include<cstdio>
#include<cctype>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;
int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
const int maxn=;
struct edge{int v,from;}e[maxn*];
int tot,first[maxn],l[maxn],r[maxn],d[maxn],root[maxn],n,m,top[maxn];
ll delta[maxn],w[maxn],ans=;
bool vis[maxn]; void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
void modify(int k,int x){delta[k]+=x;w[k]+=x;}
void down(int x){
if(delta[x]){
if(l[x])modify(l[x],delta[x]);
if(r[x])modify(r[x],delta[x]);//make 0 no influence!
delta[x]=;
}
}
int merge(int x,int y){
if(!x||!y)return x^y;
if(w[x]>w[y])swap(x,y);
down(x);r[x]=merge(r[x],y);
if(d[l[x]]<d[r[x]])swap(l[x],r[x]);
d[x]=d[r[x]]+;
return x;
}
void dfs(int x,int fa){
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa)dfs(e[i].v,x),root[x]=merge(root[x],root[e[i].v]);
vis[x]=;
if(x==)return;
while(vis[top[root[x]]])root[x]=merge(l[root[x]],r[root[x]]);
if(!root[x]){printf("-1");exit();}
ans+=w[root[x]];modify(root[x],-w[root[x]]);
}
int main(){
n=read();m=read();
for(int i=;i<n;i++){
int u=read(),v=read();
insert(u,v);insert(v,u);
}
for(int i=;i<=m;i++){
int u=read();top[i]=read();w[i]=read();
root[u]=merge(root[u],i);
}
ans=;
dfs(,);
printf("%lld",ans);
return ;
}