codesforces 671D Roads in Yusland

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 c_i coins and then he repairs all roads on a path from u_i to some v_i that lies on the path from u_i 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.

Input

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 x_i and y_i (1 ≤ x_i, y_i ≤ n) — indices of intersections connected by the i-th road.

Last m lines provide the description of workers, each line containing three integers u_i, v_i and c_i (1 ≤ u_i, v_i ≤ n, 1 ≤ c_i ≤ 10⁹). This means that the i-th worker can repair all roads on the path from v_i to u_i for c_i coins. It's guaranteed that v_i lies on the path from u_i to 1. Note that v_i and u_i may coincide.

Output

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.

Example

Input

Output

Note

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序维护以工人为下标的线段树，这样给子节点的工人加数等于线段树的区间加法

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 struct Node

 {

   int next,to;

 }edge[],edgeS[],edgeT[];

 int num,numS,numT,head[],headS[],headT[];

 int L[],R[],cnt,dfn[],n,m;

 ll c[],lazy[],val[],inf=2e15,f[];

 void add(int u,int v)

 {

   num++;

   edge[num].next=head[u];

   head[u]=num;

   edge[num].to=v;

 }

 void addS(int u,int v)

 {

   numS++;

   edgeS[numS].next=headS[u];

   headS[u]=numS;

   edgeS[numS].to=v;

 }

 void addT(int u,int v)

 {

   numT++;而且没有后效性，因为

   edgeT[numT].next=headT[u];

   headT[u]=numT;

   edgeT[numT].to=v;

 }

 void pushup(int rt)

 {

   c[rt]=min(c[rt*],c[rt*+]);

 }

 void pushdown(int rt)

 {

   if (lazy[rt])

     {

       c[rt*]+=lazy[rt];

       c[rt*+]+=lazy[rt];

       lazy[rt*]+=lazy[rt];

       lazy[rt*+]+=lazy[rt];

       lazy[rt]=;

     }

 }

 void build(int rt,int l,int r)

 {

   c[rt]=inf;

   if (l==r)

       return;

   int mid=(l+r)/;

   build(rt*,l,mid);

   build(rt*+,mid+,r);

 }

 void prework(int x,int pa)

 {int i;

   L[x]=cnt+;

   for (i=headS[x];i;i=edgeS[i].next)

     {

       int v=edgeS[i].to;

       dfn[v]=++cnt;

     }

   for (i=head[x];i;i=edge[i].next)

     {

       int v=edge[i].to;

       if (v!=pa)

     prework(v,x);

     }

   R[x]=cnt;

 }

 void update(int rt,int l,int r,int x,ll d)

 {

   if (l==r)

     {

       c[rt]=min(inf,d);

       return;

     }

   pushdown(rt);

   int mid=(l+r)/;

   if (x<=mid) update(rt*,l,mid,x,d);

   else update(rt*+,mid+,r,x,d);

   pushup(rt);

 }

 void change(int rt,int l,int r,int L,int R,ll d)

 {

   if (L>R) return;

   if (l>=L&&r<=R)

     {

       c[rt]+=d;

       c[rt]=min(c[rt],inf);

       lazy[rt]+=d;

       lazy[rt]=min(lazy[rt],inf);

       return;

     }

   pushdown(rt);

   int mid=(l+r)/;

   if (L<=mid) change(rt*,l,mid,L,R,d);

   if (R>mid) change(rt*+,mid+,r,L,R,d);

   pushup(rt);

 }

 ll query(int rt,int l,int r,int L,int R)

 {

   if (L>R) return inf;

 if (l>=L&&r<=R)

     {

       return c[rt];

     }

   pushdown(rt);

   int mid=(l+r)/;

   ll s=inf;

   if (L<=mid) s=min(s,query(rt*,l,mid,L,R));

   if (R>mid) s=min(s,query(rt*+,mid+,r,L,R));

   pushup(rt);

   return s;

 }

 void dfs(int x,int pa)

 {int i;

   ll tot=;

   for (i=head[x];i;i=edge[i].next)

     {

       int v=edge[i].to;

       if (v==pa) continue;

       dfs(v,x);

       tot+=f[v];

       tot=min(tot,inf);

     }

   if (x==)

     {

       f[]=tot;

       return;

     }

   for (i=headS[x];i;i=edgeS[i].next)

     {

       int v=edgeS[i].to;

       update(,,m,dfn[v],tot+val[v]);

     }

   for (i=headT[x];i;i=edgeT[i].next)

     {

       int v=edgeT[i].to;

       update(,,m,dfn[v],inf);

     }

   for (i=head[x];i;i=edge[i].next)

     {

       int v=edge[i].to;

       if (v==pa) continue;

       change(,,m,L[v],R[v],tot-f[v]);

     }

   f[x]=query(,,m,L[x],R[x]);

 }

 int main()

 {int i,u,v;

   cin>>n>>m;

   for (i=;i<=n-;i++)

     {

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

       add(u,v);add(v,u);

     }

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

     {

       scanf("%d%d%I64d",&u,&v,&val[i]);

       addS(u,i);addT(v,i);

     }

   prework(,);

   build(,,m);

   dfs(,);

   if (f[]!=inf) cout<<f[];

   else cout<<-;

 }

巴特西

codesforces 671D Roads in Yusland

最新文章

热门文章