【省内训练2018-12-23】Tree

【思路要点】

• 显然有最小割的模型，建图时只需要判断树上两条路径是否有交即可。
• 时间复杂度 O(NLogN+Dinic(M1​+M2​,M1​∗M2​)) 。

【代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXLOG = 22;
const int MAXP = 2005;
const int INF = 2e9;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == \'-\') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - \'0\';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar(\'-\');
	if (x > 9) write(x / 10);
	putchar(x % 10 + \'0\');
}
template <typename T> void writeln(T x) {
	write(x);
	puts(\"\");
}
struct edge {int dest, flow; unsigned pos; };
vector <edge> a[MAXP]; vector <int> b[MAXN];
int n, sa, sb;
int timer, dfn[MAXN], rit[MAXN];
int depth[MAXN], father[MAXN][MAXLOG];
int xa[MAXP], ya[MAXP], la[MAXP], va[MAXP];
int xb[MAXP], yb[MAXP], lb[MAXP], vb[MAXP];
int s, t, dist[MAXP]; unsigned curr[MAXP];
void addedge(int x, int y, int z) {
	a[x].push_back((edge) {y, z, a[y].size()});
	a[y].push_back((edge) {x, 0, a[x].size() - 1});
}
int dinic(int pos, int limit) {
	if (pos == t) return limit;
	int used = 0, tmp;
	for (unsigned &i = curr[pos]; i < a[pos].size(); i++)
		if (a[pos][i].flow != 0 && dist[pos] + 1 == dist[a[pos][i].dest] && (tmp = dinic(a[pos][i].dest, min(limit - used, a[pos][i].flow)))) {
			used += tmp;
			a[pos][i].flow -= tmp;
			a[a[pos][i].dest][a[pos][i].pos].flow += tmp;
			if (used == limit) return used;
		}
	return used;
}
bool bfs() {
	static int q[MAXP];
	int l = 0, r = 0;
	memset(dist, 0, sizeof(dist));
	dist[s] = 1, q[0] = s;
	while (l <= r) {
		int tmp = q[l];
		for (unsigned i = 0; i < a[tmp].size(); i++)
			if (dist[a[tmp][i].dest] == 0 && a[tmp][i].flow != 0) {
				q[++r] = a[tmp][i].dest;
				dist[q[r]] = dist[tmp] + 1;
			}
		l++;
	}
	return dist[t] != 0;
}
void work(int pos, int fa) {
	dfn[pos] = ++timer;
	depth[pos] = depth[fa] + 1;
	father[pos][0] = fa;
	for (int i = 1; i < MAXLOG; i++)
		father[pos][i] = father[father[pos][i - 1]][i - 1];
	for (unsigned i = 0; i < b[pos].size(); i++)
		if (b[pos][i] != fa) work(b[pos][i], pos);
	rit[pos] = timer;
}
int lca(int x, int y) {
	if (depth[x] < depth[y]) swap(x, y);
	for (int i = MAXLOG - 1; i >= 0; i--)
		if (depth[father[x][i]] >= depth[y]) x = father[x][i];
	if (x == y) return x;
	for (int i = MAXLOG - 1; i >= 0; i--)
		if (father[x][i] != father[y][i]) {
			x = father[x][i];
			y = father[y][i];
		}
	return father[x][0];
}
bool intersect(int x, int y) {
	if (dfn[lb[y]] >= dfn[la[x]] && dfn[lb[y]] <= rit[la[x]]) {
		if (dfn[xa[x]] >= dfn[lb[y]] && dfn[xa[x]] <= rit[lb[y]]) return true;
		if (dfn[ya[x]] >= dfn[lb[y]] && dfn[ya[x]] <= rit[lb[y]]) return true;
	}
	if (dfn[la[x]] >= dfn[lb[y]] && dfn[la[x]] <= rit[lb[y]]) {
		if (dfn[xb[y]] >= dfn[la[x]] && dfn[xb[y]] <= rit[la[x]]) return true;
		if (dfn[yb[y]] >= dfn[la[x]] && dfn[yb[y]] <= rit[la[x]]) return true;
	}
	return false;
}
int main() {
	freopen(\"tree.in\", \"r\", stdin);
	freopen(\"tree.out\", \"w\", stdout);
	read(n), read(sa), read(sb);
	for (int i = 1; i <= n - 1; i++) {
		int x, y; read(x), read(y);
		b[x].push_back(y);
		b[y].push_back(x);
	}
	work(1, 0);
	int ans = 0;
	s = 0, t = sa + sb + 1;
	for (int i = 1; i <= sa; i++) {
		read(xa[i]), read(ya[i]), read(va[i]), la[i] = lca(xa[i], ya[i]);
		addedge(s, i, va[i]), ans += va[i];
	}
	for (int i = 1; i <= sb; i++) {
		read(xb[i]), read(yb[i]), read(vb[i]), lb[i] = lca(xb[i], yb[i]);
		addedge(i + sa, t, vb[i]), ans += vb[i];
	}
	for (int i = 1; i <= sa; i++)
	for (int j = 1; j <= sb; j++)
		if (intersect(i, j)) {
			addedge(i, j + sa, INF);
		}
	while (bfs()) {
		memset(curr, 0, sizeof(curr));
		ans -= dinic(s, INF);
	}
	printf(\"%d\\n\", ans);
	return 0;
}