Destinations

题目大意

在一棵有 $n$ 个结点的树上，有 $m$ 个人从 $s_i$ 出发，可以选择三个目的地 $e_{i,[1,3]}$ ，分别花费 $c_{i,[1,3]}$ 。现在求一种方案使得每个点只被一个人走过且花费最小。

题解

一个人的路径是共起点的，又有每条路径没能经过相同点，那么就可以把人给忽略，直接考虑 $3m$ 条路经的选择。即简化题意：选择 $3m$ 条路径使得选择的数量最多（反正不可能超过 $m$ ）而花费最小。

考虑线性规划，把它标准化：

$$\max\{c^Tx~|~Ax\leq b,x\ge 0\} $$

$x$ 即要求的路径选择方案，每一项的值为 0 或 1。 $A$ 就是每条路径和每个点的关系， $b$ 则是每一项为 1 的向量。但是此处有个问题，不知道 $c$ 的意义：如果单纯取花费的话，不能使得选择数量最多。有一个很妙的意义是 $c$ 的每一项是一个二元组 $(x,y)$ 表示 $x$ 的数量和 $y$ 的花费，这样以 $x$ 为第一关键字比较大小就能优先考虑数量。

然后对偶：

$$\min\{y^Tb~|~A^Ty\geq c,y\geq0\} $$

由于 $b$ 一定是 1，这个 $y$ 相当于给每个点赋上了二元组权值。树状数组维护贪心求 $y$ 即可。

代码

由于航电的 OJ 打不开，我只测了样例。

const int N = 2e5 + 10;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	vector <int> e[N];
	int dep[N], dfn[N], low[N], f[N][25], cnt;
	void dfs(int u, int fa) {
		f[u][0] = fa, dfn[u] = ++cnt, dep[u] = dep[fa] + 1;
		for (int v: e[u]) {
			if (v == fa) continue;
			dfs (v, u);
		}
		low[u] = cnt;
	}
	int LCA (int u, int v) {
		if (dep[u] < dep[v]) u ^= v ^= u ^= v;
		int d = dep[u] - dep[v];
		for (int i = 20; ~i; i--) if ((d >> i) & 1) u = f[u][i];
		if (u == v) return u;
		for (int i = 20; ~i; i--) if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
		return f[v][0];
	}
#define Pair pair <ll, ll> 
	Pair a[N];
	inline Pair operator + (const Pair &x, const Pair &y) { return make_pair(x.first + y.first, x.second + y.second); }
	inline Pair operator - (const Pair &x, const Pair &y) { return make_pair(x.first - y.first, x.second - y.second); }
	inline bool operator < (const Pair &x, const Pair &y) { return x.first != y.first? x.first < y.first: x.second < y.second; }

	Pair t[N];
	void modify (int x, Pair val) { for (; x <= n; x += x&-x) t[x] = t[x] + val; }
	Pair query (int x) { Pair ans = make_pair(0, 0); for (; x; x -= x&-x) ans = ans + t[x]; return ans; }

	struct node {
		int u, v; ll w;
		node(){}
		node(int u, int v, ll w):u(u), v(v), w(w) {}
	};
	vector <node> tr[N];
	void solve (int u, int fa) {
		a[u] = make_pair(0, 0);
		for (int v: e[u]) if (v != fa) solve(v, u);
		for (node t: tr[u]) {
			Pair y = query(dfn[t.u]) + query(dfn[t.v]);
			if (y + a[u] < make_pair(1, t.w)) a[u] = make_pair(1, t.w) - y;
		}
		modify(dfn[u], a[u]);
		modify(low[u] + 1, make_pair(0, 0) - a[u]);
	}
	
	int main () {
		for (int T = Read(); T--; ) {
			n = Read(), m = Read();
			for (int i = 1; i <= n; i++) e[i].clear(), t[i] = make_pair(0, 0), tr[i].clear();
			for (int i = 1; i <= n; i++)
				for (int j = 0; j <= 20; j++) f[i][j] = 0;
			for (int i = 1; i < n; i++) {
				int u = Read(), v = Read();
				e[u].emplace_back(v);
				e[v].emplace_back(u);
			}
			cnt = 0, dep[0] = 0;
			dfs(1, 0);
			for (int j = 1; j <= 20; j++)
				for (int i = 1; i <= n; i++)
					f[i][j] = f[f[i][j-1]][j - 1];
			for (int i = 1; i <= m; i++) {
				int s = Read(), e = Read();ll c = Read(), lca = LCA(s, e);
				tr[lca].emplace_back(node(s, e, -c));
				e = Read(), c = Read(), lca = LCA(s, e);
				tr[lca].emplace_back(node(s, e, -c));
				e = Read(), c = Read(), lca = LCA(s, e);
				tr[lca].emplace_back(node(s, e, -c));
			}
			solve (1, 0);
			Pair ans = make_pair(0, 0);
			for (int i = 1; i <= n; i++) ans = ans + a[i];
			if (ans.first < m) puts("-1");
			else printf ("%lld\n", -ans.second);
		}
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}