VEXOBEN
Vexoben
Apr 29, 2019
It takes 24 minutes to read this article.

我觉得怪怪的……其实还挺好写的

题意

给定三棵个节点的树,找出两个点,,使得在三棵树这两点的距离和最大。

数据范围:,权值

题解

一棵树:直接

两棵树:第一棵树上边分治,然后问题转化为在一棵树上,每个点有一个权值表示到分治中心的距离,再给定两个点集,求分处两个点集的一个点对使得最大,直接建虚树即可。

三棵树:第一棵树上边分治,将点染为黑白两色。在第二棵树上求虚树,枚举,定义一个点在第三棵树上的权值为:第一棵树上到分治中心的距离第二棵树上到根的距离,那么一个点对的真实贡献就是。因此可以对于第二棵树上的每个节点维护以这个点为根的子树的点集在第三棵树上的直径,而两个点集的直径是可以很方便地合并的,如果实现地优秀可以做到,但是下面的代码是的。

据说在点分治的时候每次合并两个最小的联通块就相当于边分。感性理解一下好像非常有道理,但是不会严谨证明。

献上垃圾代码。

#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int, int>
using namespace std;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

int n, Log[N << 2];
LL ans;

namespace Tree1 {
	int V, E, tim;
	int fir[N << 1], nex[N << 2], arr[N << 2];
	int fa[N << 1], dep[N << 1], pos[N << 2], dfn[N << 2], mi[N << 2][19];
	LL dis[N << 1], len[N << 2];

	void Add_Edge(int x, int y, LL l) {
		nex[++E] = fir[x];
		fir[x] = E; arr[E] = y; len[E] = l;
	}

	void dfs(int x) {
		dfn[++tim] = x;
		pos[x] = tim;
		dep[x] = dep[fa[x]] + 1;
		for (int i = fir[x]; i; i = nex[i]) {
			if (arr[i] == fa[x]) continue;
			dis[arr[i]] = dis[x] + len[i];
			fa[arr[i]] = x;
			dfs(arr[i]);
			dfn[++tim] = x;
		}
	}

	int _min(int x, int y) {
		return dep[x] < dep[y] ? x : y;
	}

	int LCA(int x, int y) {
		x = pos[x], y = pos[y];
		if (x > y) swap(x, y);
		int len = Log[y - x + 1];
		return _min(mi[x][len], mi[y - (1 << len) + 1][len]);
	}

	LL dist(int x, int y) {
		if (!x || !y) return -(!x + !y);
		int lca = LCA(x, y);
		return dis[x] + dis[y] - 2 * dis[lca];
	}

	int update(int x, LL v) {
		len[fir[x]] = v;
		dis[arr[fir[x]]] = dis[x] + len[fir[x]];
	}

	void prework() {
		V = n;
		for (int i = 1; i <= n; ++i) {
			++V;
			Add_Edge(i, V, 0);
			Add_Edge(V, i, 0);
		}
		dfs(1);
		for (int i = 1; i <= tim; ++i) {
			mi[i][0] = dfn[i];
		}
		for (int j = 1; j < 19; ++j) {
			for (int i = 1; i <= tim; ++i) {
				if (i + (1 << j) - 1 > tim) continue;
				mi[i][j] = _min(mi[i][j - 1], mi[i + (1 << j - 1)][j - 1]);
			}
		}
	}
}

namespace Tree2 {
	int E, tim;
	int fir[N], nex[N << 1], arr[N << 1];
	int fa[N], dep[N], pos[N], dfn[N], use[N], book[N], type[N];
	int mi[N][19];
	LL dis[N], len[N << 1];
	vector<int> vnode, vt[N];
	
	struct dia {
		int p1, p2, p3, p4;
		dia operator + (const dia &b) const {
			dia ans;
			ans.p1 = b.p1; ans.p2 = b.p2;
			int A[4] = { p1, p2, b.p1, b.p2 };
			for (int i = 0; i < 2; ++i) {
				for (int j = i + 1; j < 4; ++j) {
					if (Tree1::dist(A[i], A[j]) > Tree1::dist(ans.p1, ans.p2)) {
						ans.p1 = A[i];
						ans.p2 = A[j];
					}
				}
			}
			ans.p3 = b.p3; ans.p4 = b.p4;
			int B[4] = { p3, p4, b.p3, b.p4 };
			for (int i = 0; i < 2; ++i) {
				for (int j = i + 1; j < 4; ++j) {
					if (Tree1::dist(B[i], B[j]) > Tree1::dist(ans.p3, ans.p4)) {
						ans.p3 = B[i];
						ans.p4 = B[j];
					}
				}
			}
			return ans;
		}
	};

	void Add_Edge(int x, int y, LL l) {
		nex[++E] = fir[x];
		fir[x] = E; arr[E] = y; len[E] = l;
	}

	void dfs(int x) {
		dfn[++tim] = x;
		pos[x] = tim;
		dep[x] = dep[fa[x]] + 1;
		for (int i = fir[x]; i; i = nex[i]) {
			if (arr[i] == fa[x]) continue;
			dis[arr[i]] = dis[x] + len[i];
			fa[arr[i]] = x;
			dfs(arr[i]);
			dfn[++tim] = x;
		}
	}

	int _min(int x, int y) {
		return dep[x] < dep[y] ? x : y;
	}

	int LCA(int x, int y) {
		x = pos[x], y = pos[y];
		if (x > y) swap(x, y);
		int len = Log[y - x + 1];
		return _min(mi[x][len], mi[y - (1 << len) + 1][len]);
	}

	LL dist(int x, int y) {
		if (!x || !y) return 0;
		int lca = LCA(x, y);
		return dis[x] + dis[y] - 2 * dis[lca];
	}

	void prework() {
		dfs(1);
		for (int i = 1; i <= tim; ++i) {
			mi[i][0] = dfn[i];
		}
		for (int j = 1; j < 19; ++j) {
			for (int i = 1; i <= tim; ++i) {
				if (i + (1 << j) - 1 > tim) continue;
				mi[i][j] = _min(mi[i][j - 1], mi[i + (1 << j - 1)][j - 1]);
			}
		}
	}

	bool cmp(int x, int y) {
		return pos[x] < pos[y];
	}
	
	void build_vitual_tree(vector<int> &A, vector<int> &B) {
		vector<int> node;
		for (int i = 0; i < A.size(); ++i) {
			node.pb(A[i]);
			use[A[i]] = 1;
		}
		for (int i = 0; i < B.size(); ++i) {
			node.pb(B[i]);
			use[B[i]] = 1;
		}
		sort(node.begin(), node.end(), cmp);
		static int top, st[N];
		st[top = 1] = 1;
		book[1] = 1;
		vnode.pb(1);
		for (int i = 0; i < node.size(); ++i) {
			if (node[i] == 1) continue;
			int x = node[i], y = LCA(node[i], st[top]);
			if (!book[x]) {
				book[x] = 1;
				vnode.pb(x);
			}
			if (!book[y]) {
				book[y] = 1;
				vnode.pb(y);
			}
			while (1) {
				if (y == st[top]) {
					st[++top] = x;
					break;
				}
				else if (dep[y] > dep[st[top - 1]]) {
 					vt[y].pb(st[top--]);
					st[++top] = y; st[++top] = x;
					break;
				}
				else if (dep[y] <= dep[st[top - 1]]) {
					vt[st[top - 1]].pb(st[top]);
					--top;
				}
			}
		}
		while (top > 1) {
			vt[st[top - 1]].pb(st[top]);
			--top;
		}
	}

	void check(int x, dia a, dia b) {
		ans = max(ans, Tree1::dist(a.p1, b.p3) - 2 * dis[x]);
		ans = max(ans, Tree1::dist(a.p1, b.p4) - 2 * dis[x]);
		ans = max(ans, Tree1::dist(a.p2, b.p3) - 2 * dis[x]);
		ans = max(ans, Tree1::dist(a.p2, b.p4) - 2 * dis[x]);
		ans = max(ans, Tree1::dist(a.p3, b.p1) - 2 * dis[x]);
		ans = max(ans, Tree1::dist(a.p3, b.p2) - 2 * dis[x]);
		ans = max(ans, Tree1::dist(a.p4, b.p1) - 2 * dis[x]);
		ans = max(ans, Tree1::dist(a.p4, b.p2) - 2 * dis[x]);
	}

	dia calc(int x) {
		dia now = (dia) { 0, 0, 0, 0 };
		if (type[x] == 1) now.p1 = x, now.p2 = x + n;
		if (type[x] == 2) now.p3 = x, now.p4 = x + n;
		for (int i = 0; i < vt[x].size(); ++i) {
			dia tmp = calc(vt[x][i]);
			check(x, now, tmp);
			now = now + tmp;
		}
		return now;
	}

	void solve(vector<int> &A, vector<int> &B) {
		build_vitual_tree(A, B);
		for (int i = 0; i < A.size(); ++i) {
			type[A[i]] = 1;
		}
		for (int i = 0; i < B.size(); ++i) {
			type[B[i]] = 2;
		}
		calc(1);
		for (int i = 0; i < vnode.size(); ++i) {
			vt[vnode[i]].clear();
			book[vnode[i]] = type[vnode[i]] = 0;
		}
		vnode.clear();
	}
}

namespace Tree3 {
	int E, G, Gsize, tot_size;
	int fir[N], nex[N << 1], arr[N << 1];
	int siz[N], alive[N];
	LL dis[N], len[N << 1];
	vector<int> node[N];

	void Add_Edge(int x, int y, LL l) {
		nex[++E] = fir[x];
		fir[x] = E; arr[E] = y; len[E] = l;
	}

	void calc_size(int x, int fa, int rt, int pos) {
		siz[x] = 1;
		for (int i = fir[x]; i; i = nex[i]) {
			if (arr[i] == fa || !alive[arr[i]]) continue;
			dis[arr[i]] = dis[x] + len[i];
			calc_size(arr[i], x, rt, pos);
			siz[x] += siz[arr[i]];
		}
		if (pos) {
			node[pos].pb(x);
		}
		if (rt) {
			Tree1::update(x, dis[x] + Tree2::dis[x]);
			ans = max(ans, dis[x] + Tree2::dist(x, rt) + Tree1::dist(x, rt));
		}
	}

	void find_G(int x, int fa) {
		int sonsize = 0;
		for (int i = fir[x]; i; i = nex[i]) {
			if (arr[i] == fa || !alive[arr[i]]) continue;
			find_G(arr[i], x);
			if (sonsize < siz[arr[i]]) {
				sonsize = siz[arr[i]];
			}
		}
		int tmp = max(tot_size - siz[x], sonsize);
		if (tmp < Gsize) {
			G = x;
			Gsize = tmp;
		}
	}

	void prework() {
		for (int i = 1; i <= n; ++i) {
			alive[i] = 1;
		}
		calc_size(1, 0, 0, 0);
		Gsize = inf;
		tot_size = siz[1];
		find_G(1, 0);
	}

	void solve(int x) {
		dis[x] = alive[x] = 0;
		Tree1::update(x, Tree2::dis[x]);
		priority_queue<pii, vector<pii>, greater<pii> > heap;
		for (int i = fir[x]; i; i = nex[i]) {
			if (!alive[arr[i]]) continue;
			dis[arr[i]] = len[i];
			calc_size(arr[i], x, x, arr[i]);
			heap.push(mp(node[arr[i]].size(), arr[i]));
		}
		while (heap.size() > 1) {
			int x = heap.top().se; heap.pop();
			int y = heap.top().se; heap.pop();
			Tree2::solve(node[x], node[y]);
			for (int i = 0; i < node[y].size(); ++i) {
				node[x].pb(node[y][i]);
			}
			node[y].clear();
			heap.push(mp(node[x].size(), x));
		}
		if (!heap.empty()) {
			int y = heap.top().se; heap.pop();
			node[y].clear();
		}
		for (int i = fir[x]; i; i = nex[i]) {
			if (!alive[arr[i]]) continue;
			Gsize = inf;
			tot_size = siz[arr[i]];
			find_G(arr[i], x);
			solve(G);
		}
	}
}

int main() {
	read(n);
	for (int i = 1; i < n; ++i) {
		LL u, v, w;
		read(u); read(v); read(w);
		Tree1::Add_Edge(u, v, w);
		Tree1::Add_Edge(v, u, w);
	}
	for (int i = 1; i < n; ++i) {
		LL u, v, w;
		read(u); read(v); read(w);
		Tree2::Add_Edge(u, v, w);
		Tree2::Add_Edge(v, u, w);
	}
	for (int i = 1; i < n; ++i) {
		LL u, v, w;
		read(u); read(v); read(w);
		Tree3::Add_Edge(u, v, w);
		Tree3::Add_Edge(v, u, w);
	}
	Log[1] = 0;
	for (int i = 2; i < (N << 2); ++i) {
		Log[i] = Log[i >> 1] + 1;
	}
	Tree1::prework();
	Tree2::prework();
	Tree3::prework();
	Tree3::solve(Tree3::G);
	printf("%lld\n", ans);
	return 0;
}