Mayor of Yusland just won the lottery and decided to spent money on something good for town. For example, repair all the roads in the town.
Yusland consists of n intersections connected by n - 1 bidirectional roads. One can travel from any intersection to any other intersection using only these roads.
There is only one road repairing company in town, named "RC company". Company's center is located at the intersection 1. RC company doesn't repair roads you tell them. Instead, they have workers at some intersections, who can repair only some specific paths. The i-th worker can be paid ci coins and then he repairs all roads on a path from ui to some vi that lies on the path from ui to intersection 1.
Mayor asks you to choose the cheapest way to hire some subset of workers in order to repair all the roads in Yusland. It's allowed that some roads will be repaired more than once.
If it's impossible to repair all roads print - 1.
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 300 000) — the number of cities in Yusland and the number of workers respectively.
Then follow n−1 line, each of them contains two integers xi and yi (1 ≤ xi, yi ≤ n) — indices of intersections connected by the i-th road.
Last m lines provide the description of workers, each line containing three integers ui, vi and ci (1 ≤ ui, vi ≤ n, 1 ≤ ci ≤ 109). This means that the i-th worker can repair all roads on the path from vi to ui for ci coins. It's guaranteed that vi lies on the path from ui to 1. Note that vi and ui may coincide.
If it's impossible to repair all roads then print - 1. Otherwise print a single integer — minimum cost required to repair all roads using "RC company" workers.
6 5 1 2 1 3 3 4 4 5 4 6 2 1 2 3 1 4 4 1 3 5 3 1 6 3 2
8
In the first sample, we should choose workers with indices 1, 3, 4 and 5, some roads will be repaired more than once but it is OK. The cost will be equal to 2 + 3 + 1 + 2 = 8 coins.
设f[i]为控制了i点的子树的费用
显然f是存在后效性的，因为当前选的工人会影响祖先的状态
最暴力的方法f[x][i]表示工人最高控制到x，控制了i的子树，不过显然超时
想办法消除后效性
我们考虑把一些工人的属性叠加到一个工人上，那么我们最后查询时只要查询某些能维修完整棵树的最小值
因为我们已经的到了这几棵子树的最优答案，并且子树之间互不影响，那么我们考虑把控制其他子树费用叠加到一个子树工人上
假设儿子有p1,p2,p3，tot=∑f[p]
p1的儿子的工人加上tot-f[p1]，其他同理
也就是说，每一个工人都有控制其他所有子树的花费
也就是说，祖先x要用到p儿子这个工人时，就可以直接算出控制p儿子及x的费用
而且没有后效性，因为工人存了包含此工人的最优解，而且工人一直到vi被消掉之前，
都可以覆盖当前点，所以把工人都计算，肯定能算出最优解
因为工人在到vi之前都需要
而且对于计算一个节点的f，我们要给开始的工人赋值，给结束的工人消值，且给子节点所有工人加数
所以我们用dfs序维护以工人为下标的线段树，这样给子节点的工人加数等于线段树的区间加法
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 typedef long long ll; 7 struct Node 8 { 9 int next,to; 10 }edge[600101],edgeS[600101],edgeT[600101]; 11 int num,numS,numT,head[300011],headS[300011],headT[300011]; 12 int L[300011],R[300011],cnt,dfn[300011],n,m; 13 ll c[1200101],lazy[1200101],val[300011],inf=2e15,f[300011]; 14 void add(int u,int v) 15 { 16 num++; 17 edge[num].next=head[u]; 18 head[u]=num; 19 edge[num].to=v; 20 } 21 void addS(int u,int v) 22 { 23 numS++; 24 edgeS[numS].next=headS[u]; 25 headS[u]=numS; 26 edgeS[numS].to=v; 27 } 28 void addT(int u,int v) 29 { 30 numT++;而且没有后效性，因为 31 edgeT[numT].next=headT[u]; 32 headT[u]=numT; 33 edgeT[numT].to=v; 34 } 35 void pushup(int rt) 36 { 37 c[rt]=min(c[rt*2],c[rt*2+1]); 38 } 39 void pushdown(int rt) 40 { 41 if (lazy[rt]) 42 { 43 c[rt*2]+=lazy[rt]; 44 c[rt*2+1]+=lazy[rt]; 45 lazy[rt*2]+=lazy[rt]; 46 lazy[rt*2+1]+=lazy[rt]; 47 lazy[rt]=0; 48 } 49 } 50 void build(int rt,int l,int r) 51 { 52 c[rt]=inf; 53 if (l==r) 54 return; 55 int mid=(l+r)/2; 56 build(rt*2,l,mid); 57 build(rt*2+1,mid+1,r); 58 } 59 void prework(int x,int pa) 60 { int i; 61 L[x]=cnt+1; 62 for (i=headS[x];i;i=edgeS[i].next) 63 { 64 int v=edgeS[i].to; 65 dfn[v]=++cnt; 66 } 67 for (i=head[x];i;i=edge[i].next) 68 { 69 int v=edge[i].to; 70 if (v!=pa) 71 prework(v,x); 72 } 73 R[x]=cnt; 74 } 75 void update(int rt,int l,int r,int x,ll d) 76 { 77 if (l==r) 78 { 79 c[rt]=min(inf,d); 80 return; 81 } 82 pushdown(rt); 83 int mid=(l+r)/2; 84 if (x<=mid) update(rt*2,l,mid,x,d); 85 else update(rt*2+1,mid+1,r,x,d); 86 pushup(rt); 87 } 88 void change(int rt,int l,int r,int L,int R,ll d) 89 { 90 if (L>R) return; 91 if (l>=L&&r<=R) 92 { 93 c[rt]+=d; 94 c[rt]=min(c[rt],inf); 95 lazy[rt]+=d; 96 lazy[rt]=min(lazy[rt],inf); 97 return; 98 } 99 pushdown(rt);100 int mid=(l+r)/2;101 if (L<=mid) change(rt*2,l,mid,L,R,d);102 if (R>mid) change(rt*2+1,mid+1,r,L,R,d);103 pushup(rt);104 }105 ll query(int rt,int l,int r,int L,int R)106 {107 if (L>R) return inf;108 if (l>=L&&r<=R)109 {110 return c[rt];111 }112 pushdown(rt);113 int mid=(l+r)/2;114 ll s=inf;115 if (L<=mid) s=min(s,query(rt*2,l,mid,L,R));116 if (R>mid) s=min(s,query(rt*2+1,mid+1,r,L,R));117 pushup(rt);118 return s;119 }120 void dfs(int x,int pa)121 { int i;122 ll tot=0;123 for (i=head[x];i;i=edge[i].next)124 {125 int v=edge[i].to;126 if (v==pa) continue;127 dfs(v,x);128 tot+=f[v];129 tot=min(tot,inf);130 }131 if (x==1) 132 {133 f[1]=tot;134 return;135 }136 for (i=headS[x];i;i=edgeS[i].next)137 {138 int v=edgeS[i].to;139 update(1,1,m,dfn[v],tot+val[v]);140 }141 for (i=headT[x];i;i=edgeT[i].next)142 {143 int v=edgeT[i].to;144 update(1,1,m,dfn[v],inf);145 }146 for (i=head[x];i;i=edge[i].next)147 {148 int v=edge[i].to;149 if (v==pa) continue;150 change(1,1,m,L[v],R[v],tot-f[v]);151 }152 f[x]=query(1,1,m,L[x],R[x]);153 }154 int main()155 { int i,u,v;156 cin>>n>>m;157 for (i=1;i<=n-1;i++)158 {159 scanf("%d%d",&u,&v);160 add(u,v);add(v,u);161 }162 for (i=1;i<=m;i++)163 {164 scanf("%d%d%I64d",&u,&v,&val[i]);165 addS(u,i);addT(v,i);166 }167 prework(1,0);168 build(1,1,m);169 dfs(1,0);170 if (f[1]!=inf) cout<