Description：

求： $$ \max(dep_1[x]+dep_1[y]-(dep_1[LCA_1(x,y)]+dep_2[LCA_2(x,y)])) $$ $1\leqslant n\leqslant 10^5$

Solution：

通过这题学习一下边分树合并。

首先把式子化成： $$ \frac 1 2(dep_1[x]+dep_1[y]+dis_1(x,y))-dep_2[LCA_2(x,y)] $$ 这时我们可以沿用通道那道题的做法，对第一棵树进行边分治，把两边的集合合起来在第二棵树上建虚树，然后树形 $DP$ 枚举第二棵树的 $LCA$ 然后维护直径。

但是复杂度是 $O(n\log^2n)$ 的，而且不够优美。

还是在第二棵树上枚举 $LCA_2(x,y)$ ，然后我们的问题就变成了在第二棵树的这个点的子树中找两个点，要求他们来自不同的子树，并且最大化前面那个值，但是这些都不可避免地会要求在第一棵树上边分治，然后再第二棵树上虚树 $DP$ ，但是我们可以考虑把这个顺序换过来，也就是说现在第二棵树上 $dfs$ 枚举 $LCA_2(x,y)$ ，然后对于要合并的这些点拿出来在第一棵树上边分治，然后以相同的方式求答案，但是我们不用真的每次都边分治，可以使用边分树合并的方式来进行类似边分治的操作。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 750010

typedef long long ll;

#define INF 0x3f3f3f3f

#define INFLL 0x3f3f3f3f3f3f3f3f

namespace T1

{

	struct edge

	{

		int to,nxt,v;

	}ep[MAXN << 1];

	int edgenump = 0;

	int linp[MAXN] = {0};

	void addp(int a,int b,int c)

	{

		ep[++edgenump] = (edge){b,linp[a],c};linp[a] = edgenump;

		ep[++edgenump] = (edge){a,linp[b],c};linp[b] = edgenump;

		return;

	}

	edge e[MAXN << 1];

	int edgenum = 1;

	int lin[MAXN] = {0};

	void add(int a,int b,int c)

	{

		e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

		return;

	}

	ll dist[MAXN];

	int pn;

	void dfs(int k,int fa)

	{

		int s = 0;

		for(int i = linp[k];i != 0;i = ep[i].nxt)

		{

			if(ep[i].to == fa)continue;

			dist[ep[i].to] = dist[k] + ep[i].v;

			if(s == 0)add(k,ep[i].to,ep[i].v),s = k;

			else ++pn,add(s,pn,0),add(pn,ep[i].to,ep[i].v),s = pn;

			dfs(ep[i].to,k);

		}

		return;

	}

	int siz[MAXN];

	bool vis[MAXN << 1];

	int edg,s,mx;

	void getsiz(int k,int fa)

	{

		siz[k] = 1;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].to == fa || vis[i])continue;

			getsiz(e[i].to,k);

			siz[k] += siz[e[i].to];

		}

		return;

	}

	void getedg(int k,int fa)

	{

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].to == fa || vis[i])continue;

			getedg(e[i].to,k);

			int d = max(s - siz[e[i].to],siz[e[i].to]);

			if(d < mx)edg = i,mx = d;

		}

		return;

	}

	int find_edge(int k)

	{

		getsiz(k,0);

		s = siz[k];mx = INF;edg = -1;

		getedg(k,0);

		return edg;

	}

	int dep[MAXN];

	ll f[MAXN][20];

	void getdis(int k,int fa,int d)

	{

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].to == fa || vis[i])continue;

			f[e[i].to][d] = f[k][d] + e[i].v;

			getdis(e[i].to,k,d);

		}

		return;

	}

	#define MAXP (MAXN * 33)

	int rt,lc[MAXP],rc[MAXP],fa[MAXP];

	ll val[MAXP],fl[MAXP],fr[MAXP];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int solve(int k,int d)

	{

		int ed = find_edge(k);

		if(ed == -1){dep[k] = d;return k;}

		int rt = newnode();

		vis[ed] = vis[ed ^ 1] = true;

		int u = e[ed].to,v = e[ed ^ 1].to;

		getdis(u,0,d);getdis(v,0,d);

		val[rt] = e[ed].v;

		fa[lc[rt] = solve(u,d + 1)] = rt;

		fa[rc[rt] = solve(v,d + 1)] = rt;

		return rt;

	}

	int root[MAXN];

	int insert(int k)

	{

		int last = k;

		for(int i = dep[k] - 1,p = k;i >= 1;--i)

		{

			int cur = newnode();

			val[cur] = val[fa[p]];

			fl[cur] = fr[cur] = -INFLL;

			if(lc[fa[p]] == p)fl[cur] = max(fl[cur],dist[k] + f[k][i]),lc[cur] = last;

			if(rc[fa[p]] == p)fr[cur] = max(fr[cur],dist[k] + f[k][i]),rc[cur] = last;

			p = fa[p];last = cur;

		}

		return last;

	}

	ll ans,D;

	int merge(int x,int y)

	{

		if(x == 0)return y;if(y == 0)return x;

		ans = max(ans,(fl[x] + fr[y] + val[x]) / 2 - D);

		ans = max(ans,(fl[y] + fr[x] + val[x]) / 2 - D);

		fl[x] = max(fl[x],fl[y]);fr[x] = max(fr[x],fr[y]);

		lc[x] = merge(lc[x],lc[y]);

		rc[x] = merge(rc[x],rc[y]);

		return x;

	}

	void build_tree()

	{

		pn = n;

		dfs(1,0);

		ptr = pn;

		rt = solve(1,1);

		for(int i = 1;i <= n;++i)root[i] = insert(i);

		return;

	}

}

namespace T2

{

	struct edge

	{

		int to,nxt,v;

	}e[MAXN << 1];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b,int c)

	{

		e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

		return;

	}

	ll dist[MAXN];

	void dfs(int k,int fa)

	{

		T1::ans = max(T1::ans,T1::dist[k] - dist[k]);

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].to == fa)continue;

			dist[e[i].to] = dist[k] + e[i].v;

			dfs(e[i].to,k);

			T1::D = dist[k];

			T1::root[k] = T1::merge(T1::root[k],T1::root[e[i].to]);

		}

		return;

	}

}

int main()

{

	scanf("%d",&n);

	int a,b,c;

	for(int i = 1;i < n;++i)scanf("%d%d%d",&a,&b,&c),T1::addp(a,b,c);

	for(int i = 1;i < n;++i)scanf("%d%d%d",&a,&b,&c),T2::add(a,b,c);

	T1::build_tree();

	T2::dfs(1,0);

	cout << T1::ans << endl;

	return 0;

}