神tm部分分可过。
首先这个式子先两倍变成\(d_x+d_y+dist(x,y)-2d'_{LCA(x,y)}\)
如果我们按照情报中心那题的方法，枚举\(LCA(x,y)\)，将\(d_x\)看成\(x\)的点权，\(d_y\)看成\(y\)的点权，合并第一棵树上最远点对，那么恭喜你，应该得到40pts，原因是用两个点维护最远点对只能在权值为正的情况下做。
那为什么是应该呢？因为在这道题里它过了……
正确做法应该是在第一棵树上点分，前面的\(d_x+d_y+dist(x,y)\)就可以转化成一个两个点独立的贡献，这时候将这些点在第二棵树上建虚树，在LCA处合并答案即可。
注意子树内不能算答案，因此要记录颜色，并要保留最大值和颜色不同的次大值。
时间复杂度\(O(n\log^2 n)\)。
code:
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=4e5+5,M=(1<<20)+5,K=1e5+5,mod=998244353,Mod=mod-1;const ll INF=1e18+7;const db eps=1e-5;mt19937 rnd(time(0));
struct IO{
static const int S=1<<21;
char buf[S],*p1,*p2;int st[105],Top;
~IO(){clear();}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
template<typename T>inline IO&operator >> (T&x){
x=0;bool f=0;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;return *this;
}
inline IO&operator << (const char c){pc(c);return *this;}
template<typename T>inline IO&operator << (T x){
if(x<0) pc('-'),x=-x;
do{st[++st[0]]=x%10,x/=10;}while(x);
while(st[0]) pc('0'+st[st[0]--]);return *this;
}
}fin,fout;
int n,m,k,x,y,z,col[N],B[N],Bh;ll Ans,W1[N],W2[N],Sum[N];
struct Edge{int to,w;};vector<Edge> S1[N],S2[N];vector<int> G[N];
namespace ER{
int st[N],sh,Id[N*2][20],d[N],lg[N*2],Bg[N],Dh,Df[N*2],Fl[N],f[N][2];
void Make(int x,int La){Df[Bg[x]=++Dh]=x;d[x]=d[La]+1;for(Edge i:S2[x]) i.to^La&&(W2[i.to]=W2[x]+i.w,Make(i.to,x),Df[++Dh]=x);}
void BD(){
int i,j;Make(1,0);for(i=2;i<=Dh;i++) lg[i]=lg[i/2]+1;
for(i=Dh;i;i--){
for(Id[i][0]=Df[i],j=1;i+(1<<j)-1<=Dh;j++) Id[i][j]=(d[Id[i][j-1]]<d[Id[i+(1<<j-1)][j-1]]?Id[i][j-1]:Id[i+(1<<j-1)][j-1]);
}
}
int LCA(int x,int y){x=Bg[x];y=Bg[y];x>y&&(swap(x,y),0);int D=lg[y-x+1];return d[Id[x][D]]<d[Id[y-(1<<D)+1][D]]?Id[x][D]:Id[y-(1<<D)+1][D];}
bool cmp(int x,int y){return Bg[x]<Bg[y];}void con(int x,int y){G[x].PB(y);}
void dfs(int x){
if(Fl[x]) f[x][0]=x;for(int i:G[x]){
dfs(i);
for(int j=0;j<2;j++) for(int h=0;h<2;h++) if(f[x][j]&&f[i][h]&&col[f[x][j]]^col[f[i][h]]) Ans=max(Ans,Sum[f[x][j]]+Sum[f[i][h]]-2*W2[x]);
for(int j=0;j<2;j++) if(f[i][j]){
if(!f[x][0]) f[x][0]=f[i][j];
else if(Sum[f[i][j]]>Sum[f[x][0]]) col[f[i][j]]^col[f[x][0]]&&(f[x][1]=f[x][0]),f[x][0]=f[i][j];
else if(!f[x][1]&&col[f[i][j]]^col[f[x][0]]) f[x][1]=f[i][j];
else if(Sum[f[i][j]]>Sum[f[x][1]]&&col[f[i][j]]^col[f[x][0]]) f[x][1]=f[i][j];
}
}
}
void Cl(int x){Fl[x]=0;f[x][0]=f[x][1]=0;for(int i:G[x]) Cl(i);G[x].clear();}
void GA(){
int i,j;for(i=1;i<=Bh;i++) Fl[B[i]]=1;B[++Bh]=1;sort(B+1,B+Bh+1,cmp);Bh=unique(B+1,B+Bh+1)-B-1;
st[sh=1]=1;for(i=2;i<=Bh;i++){
int Ls=LCA(st[sh],B[i]);while(sh>1&&d[st[sh-1]]>=d[Ls]) con(st[sh-1],st[sh]),sh--;
if(st[sh]^Ls) con(Ls,st[sh]),st[sh]=Ls;st[++sh]=B[i];
}while(sh>1) con(st[sh-1],st[sh]),sh--; dfs(1);Cl(1);
}
}
struct yyy{int to,w,z;};struct ljb{int head,h[N];yyy f[N*2];void add(int x,int y,int z){f[++head]=(yyy){y,z,h[x]};h[x]=head;}}s;
void Make(int x,int La){for(Edge i:S1[x]) i.to^La&&(W1[i.to]=W1[x]+i.w,Make(i.to,x),0);}
namespace TDQ{
int Ct,Rt,Si[N],f[N],vis[N];
void GI(int x,int La){Ct++;yyy tmp;for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^La&&!vis[tmp.to]&&(GI(tmp.to,x),0);}
void DP(int x,int La){Si[x]=1;f[x]=0;yyy tmp;for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^La&&!vis[tmp.to]&&(DP(tmp.to,x),Si[x]+=Si[tmp.to],f[x]=max(f[x],Si[tmp.to]));f[x]=max(f[x],Ct-Si[x]);f[x]<f[Rt]&&(Rt=x);}
void Ins(int x,int La,int w){B[++Bh]=x;col[x]=w;yyy tmp;for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^La&&!vis[tmp.to]&&(Sum[tmp.to]=Sum[x]+tmp.w,Ins(tmp.to,x,w),0);Sum[x]+=W1[x];Ans=max(Ans,Sum[x]+Sum[Rt]-2*W2[ER::LCA(x,Rt)]);}
void GA(int x){
Ct=0;GI(x,0);f[Rt=0]=1e9;DP(x,0);vis[x=Rt]=1;Ans=max(Ans,2*(W1[x]-W2[x]));yyy tmp;
Bh=0;int Pt=0;Sum[x]=W1[x];for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],!vis[tmp.to]&&(Sum[tmp.to]=tmp.w,Ins(tmp.to,x,++Pt),0);
ER::GA();Sum[x]=0;for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],!vis[tmp.to]&&(GA(tmp.to),0);
}
}
int main(){
freopen("wronganswer.in","r",stdin);freopen("wronganswer.out","w",stdout);
int i,j;scanf("%d",&n);for(i=1;i<n;i++) fin>>x>>y>>z,S1[x].PB((Edge){y,z}),S1[y].PB((Edge){x,z}),s.add(x,y,z),s.add(y,x,z);
for(i=1;i<n;i++) fin>>x>>y>>z,S2[x].PB((Edge){y,z}),S2[y].PB((Edge){x,z});
Ans=-INF;ER::BD();Make(1,0);TDQ::GA(1);printf("%lld\n",Ans/2);
}