Codeforces 671D Roads in Yusland

Description

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.

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 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.

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.

input

output

题意

给一颗树，给定m对祖先节点关系。每选用一对关系需要付出c的花费，求用这些关系将所有边都覆盖的最小花费。

本题有 $nlog(n)$ 树DP做法请看CF671D 树形DP+数据结构优化DP

这里我想说一下 $nlog(n)$ 的贪心做法

我们将修路转化为修点， 1 号点不用修
首先我们设$x_i$为第$i$个工人的使用次数。那么显然$x_i \geq 0$
然设一个$A$矩阵如果第$j$个工人能覆盖到第$i$点那么$A_{i,j}=1$否则$A_{i,j}=0$
那么很显然对于$(\forall 2 <= i <= n)$都有$\sum_{j = 1}^{m}{A_{i,j}*x_j} > 0$

如果将这个过程看作矩阵乘，将x看作m行1列的矩阵
那么
$$\begin{bmatrix} A_{1,1} & A_{1,2} & A_{1,3} & \cdots & A_{1,m} \\ A_{2,1} & A_{2,2} & A_{2,3} & \cdots & A_{2,m} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ A_{n,1} & A_{n,2} & A_{n,3} & \cdots & A_{n,m} \\ \end{bmatrix}
\begin{bmatrix} x_{1,1} \\ x_{1,2} \\ x_{1,3} \\ \vdots \\ x_{1,m} \\ \end{bmatrix} \geq \begin{bmatrix} 1 \\ 1 \\ 1 \\ \vdots \\ 1 \\ \end{bmatrix}$$

我们设右边的矩阵为$e$

那么我们要求的答案为
$$ min\{\sum_{j=1}^{m}c_j * x_j\} $$

如果将c看作矩阵则答案为
$min\{c^Tx\}$

那么我们发现他是一个线性规划问题。
我们可以考虑它的对偶问题。
由于对偶问题求得到函数值与原问题相等，那么我们只需要求出对偶问题的答案。

下面说一下对偶问题的构造

给每个原始约束条件定义一个非负对偶变量$y_i (i=1,2,…,m)$;
使原问题的目标函数系数cj变为其对偶问题约束条件的右端常数
使原问题约束条件的右端常数bi变为其对偶问题目标函数的系数；
将原问题约束条件的系数矩阵转置，得到其对偶问题约束条件的系数矩阵；
改变约束条件不等号的方向，即将”=<”改为”>=”；
原问题“max”型，对偶问题为“min”型．反之亦然.

那么本题的对偶问题为

$y >= 0$
$A^Ty <= c$

求$ max\{e^Ty\} $
$e$ 是上文中设的矩阵

那么用人话说就是

每个点可以选多次一个工人的路径上的点的选择次数的和在$c_i$以内，求所有点选择次数的最大和。

我们可以贪心的由下向上选取。
用一个set启发式合并就可以了。

时间复杂度$nlog(n)$ 常数略大。

// #pragma GCC optimize("O3")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int MAXN = 300005;
char xch,xB[1<<15],*xS=xB,*xTT=xB;
#define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
struct edge
{
    int END, next;
}v[MAXN << 1];
int first[MAXN], p;
void add(int a, int b)
{
    v[p].END = b;
    v[p].next = first[a];
    first[a] = p++;
}
struct data
{
    int v, cnt;
    data(int c = 0, int cn = 0)
    {
        v = c, cnt = cn;
    }
    bool operator < (const data &a) const
    {
        return cnt == a.cnt ? v < a.v : cnt < a.cnt;
    }
};
vector<data> Add[MAXN], rm[MAXN];
set<data> st[MAXN];
long long ans;
int C[MAXN], Ad[MAXN];
bool died;
void dfs(int rt, int fa)
{
    set<data>::iterator it;
    for (int i = 0; i < Add[rt].size(); i++)
        st[rt].insert(Add[rt][i]);
    for (int i = first[rt]; i != -1; i = v[i].next)
    {
        if (v[i].END == fa) continue;
        dfs(v[i].END, rt);
        if (died) return;
        if (st[v[i].END].size() > st[rt].size())
            swap(st[v[i].END], st[rt]), swap(Ad[v[i].END], Ad[rt]);
        for (it = st[v[i].END].begin(); it != st[v[i].END].end(); it++)
            st[rt].insert(data(it->v, C[it->v] = it->cnt - Ad[v[i].END] + Ad[rt]));
    }
    for (int i = 0; i < rm[rt].size(); i++)
        st[rt].erase(data(rm[rt][i].v, C[rm[rt][i].v]));
    if (rt == 1) return;
    if (st[rt].empty()) {died = 1; return;}
    ans += st[rt].begin()->cnt - Ad[rt];
    Ad[rt] += st[rt].begin()->cnt - Ad[rt];
}
signed main()
{
    int n = read(), m = read(), a, b, c;
    memset (first, -1, sizeof (first));
    for (int i = 1; i < n; i++)
    {
        a = read(), b = read();
        add(a, b);
        add(b, a);
    }
    for (int i = 1; i <= m; i++)
    {
        a = read(), b = read(), c = read();
        Add[a].push_back(data(i, c));
        rm[b].push_back(data(i, c));
        C[i] = c;
    }
    dfs(1, 0);
    if (died) printf ("-1");
    else printf ("%lld", ans);
}