设 \(f_{u,i}\) 表示覆盖了以 \(u\) 为根的子树内的所有边，且向上覆盖到了 \(u\) 深度为 \(i\) 的祖先的最小代价。
对于 \(u\) 和其儿子 \(v\)，不难合并 \[
f'_{u,i} = \min\left[\min\limits_{j=i}^n (f_{u,i} + f_{v,j}),\min\limits_{j=i}^n (f_{u,j} + f_{v,i})\right]
\]
容易线段树合并维护，但是有很多细节（
比如我到现在也不知道为什么不判掉 \(u_i = v_i\) 的条件会 WA……
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
using namespace std;
const int N = 3e5;
int n,m;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
namespace SEG
{
struct node
{
long long val,tag;
int ls,rs;
} seg[N * 30 + 5];
inline void push(int p)
{
if(seg[p].tag)
{
if(seg[p].ls)
seg[seg[p].ls].val = min(seg[seg[p].ls].val + seg[p].tag,0x3f3f3f3f3f3f3f3f),
seg[seg[p].ls].tag = min(seg[seg[p].ls].tag + seg[p].tag,0x3f3f3f3f3f3f3f3f);
if(seg[p].rs)
seg[seg[p].rs].val = min(seg[seg[p].rs].val + seg[p].tag,0x3f3f3f3f3f3f3f3f),
seg[seg[p].rs].tag = min(seg[seg[p].rs].tag + seg[p].tag,0x3f3f3f3f3f3f3f3f);
seg[p].tag = 0;
}
}
void insert(int x,long long k,int &p,int tl,int tr)
{
static int tot = 0;
!p && (seg[p = ++tot] = seg[0],1),seg[p].val = min(seg[p].val,k);
if(tl == tr)
return ;
push(p);
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
void clear(int x,int p,int tl,int tr)
{
if(!p)
return ;
if(tl == tr)
{
seg[p].val = 0x3f3f3f3f3f3f3f3f;
return ;
}
push(p);
int mid = tl + tr >> 1;
x <= mid ? clear(x,seg[p].ls,tl,mid) : clear(x,seg[p].rs,mid + 1,tr);
seg[p].val = min(seg[seg[p].ls].val,seg[seg[p].rs].val);
}
long long query(int l,int p,int tl,int tr)
{
if(!p || l <= tl)
return seg[p].val;
push(p);
int mid = tl + tr >> 1;
long long ret = 0x3f3f3f3f3f3f3f3f;
l <= mid && (ret = min(ret,query(l,seg[p].ls,tl,mid)));
ret = min(ret,query(l,seg[p].rs,mid + 1,tr));
return ret;
}
int merge(int p,int q,long long ptag,long long qtag,int tl,int tr)
{
if(!p && !q)
return 0;
if(!p)
{
seg[q].val = min(seg[q].val + qtag,0x3f3f3f3f3f3f3f3f),
seg[q].tag = min(seg[q].tag + qtag,0x3f3f3f3f3f3f3f3f);
return q;
}
if(!q)
{
seg[p].val = min(seg[p].val + ptag,0x3f3f3f3f3f3f3f3f),
seg[p].tag = min(seg[p].tag + ptag,0x3f3f3f3f3f3f3f3f);
return p;
}
if(tl == tr)
{
ptag = min(ptag,seg[q].val),qtag = min(qtag,seg[p].val);
seg[p].val = min(min(seg[p].val + ptag,seg[q].val + qtag),0x3f3f3f3f3f3f3f3f);
return p;
}
push(p),push(q);
int mid = tl + tr >> 1;
long long prval = seg[seg[p].rs].val;
long long qrval = seg[seg[q].rs].val;
seg[p].ls = merge(seg[p].ls,seg[q].ls,min(ptag,qrval),min(qtag,prval),tl,mid);
seg[p].rs = merge(seg[p].rs,seg[q].rs,ptag,qtag,mid + 1,tr);
seg[p].val = min(seg[seg[p].ls].val,seg[seg[p].rs].val);
return p;
}
}
vector<pair<int,int>> top[N + 5];
int fa[N + 5],dep[N + 5];
int rt[N + 5];
void dfs(int p)
{
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
fa[to[i]] = p,dep[to[i]] = dep[p] + 1,
dfs(to[i]),
SEG::clear(dep[to[i]],rt[to[i]],1,n),
!rt[p] ? (rt[p] = rt[to[i]]) : (rt[p] = SEG::merge(rt[p],rt[to[i]],0x3f3f3f3f3f3f3f3f,0x3f3f3f3f3f3f3f3f,1,n));
for(auto u : top[p])
SEG::insert(dep[u.first],min(u.second + (pre[first[p]] ? SEG::query(dep[u.first],rt[p],1,n) : 0),0x3f3f3f3f3f3f3f3f),rt[p],1,n);
}
int main()
{
SEG::seg[0].val = 0x3f3f3f3f3f3f3f3f;
scanf("%d%d",&n,&m);
if(n == 1)
{
puts("0");
return 0;
}
int u,v;
for(register int i = 2;i <= n;++i)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
int c;
for(;m;--m)
scanf("%d%d%d",&u,&v,&c),u ^ v && (top[u].push_back(make_pair(v,c)),1);
dep[1] = 1,dfs(1);
printf("%lld\n",SEG::seg[rt[1]].val == 0x3f3f3f3f3f3f3f3f ? -1 : SEG::seg[rt[1]].val);
}