没有代码能力...
题意
给定三棵树$ T1,T2,T3$，求一个点对$ (x,y)$使得$ T1.dist(x,y)+T2.dist(x,y)+T3.dist(x,y)$最大
每棵树的点数为$ 10^5$，时限$ 4s$
$ Solution$
尝试对$ T1$边分治
设当前分治到边$(L,R)$
将$ L$及$ L$所在一侧的点染黑，将$ R$及$ R$所在一侧的点染白
问题转化为找到一个点对$ (x,y)$使得满足$ x$为黑点$ y$为白点
并且最大化
$ T1.dist(x,L)+T1.dist(y,R)+len(x,y)+T2.dist(x,y)+T3.dist(x,y)$
考虑将所有黑白点拿出来在$ T2$上构一棵虚树
在虚树上$ DP$
有一些不那么显然的性质：
设两端均为黑色的最长路径的两个端点为$ (B1,B2)$,两端均为白色的最长路径的两个端点为$ (W1,W2)$
则两端异色的最长路径的两个端点一定在$ B1,B2,W1,W2$中出现过
设点集$ S$的黑色最长路径的两个端点为$ (B1,B2)$,点集$ T$的黑色最长路径的两个端点为$ (B3,B4)$
则点集$ S \cup T$的黑色最长路径的两个端点一定在$ B1,B2,B3,B4$中出现过
用这两个性质就可以在虚树上$ DP$了
形象化地，设我们在虚树上枚举点对在$ T2$上的$ LCA$
则这个点对一定来自于枚举的$ LCA$的不同子树
在每个子树记录黑色/白色最长路径的端点然后合并转移即可
时间复杂度$ O(n \ log^2 \ n)$
$my \ code$
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define M 500010
#define rt register int
#define ll long long
using namespace std;
namespace fast_IO{
const int IN_LEN=,OUT_LEN=;
char ibuf[IN_LEN],*ih=ibuf+IN_LEN,*lastin=ibuf+IN_LEN;
inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
}
using namespace fast_IO;
#define getchar() getchar_()
inline ll read(){
ll x=;char zf=;char ch=getchar();
while(ch!='-'&&!isdigit(ch))ch=getchar();
if(ch=='-')zf=-,ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();return x*zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,B,W,la;ll ans;
int sorttable[M];ll dist[M];
bool cmp(int x,int y){return sorttable[x]<sorttable[y];}
int sz[M],A[M],col[M];bool vis[M];
int nowmin,all,ed,sum,Root;
struct node{int a;ll c;};
vector<node>e[M];
struct tree{
int F[M],L[M],N[M],a[M],dfn[M],q[M],size[M],k=,t=,cnt=;ll deep[M],c[M];
int st[][M],fa[M],lg2[M],fir[M],dep[M];
void clear(){
for(rt i=;i<=k;i++)F[a[i]]=,N[i]=;
F[Root]=;k=;t=;cnt=;
}
void add(int x,int y,ll z){
a[++k]=y;c[k]=z;
if(!F[x])F[x]=k;
else N[L[x]]=k;
L[x]=k;
}
void dfs(int x,int pre){
q[++t]=x;dfn[x]=++cnt;size[x]=;fa[x]=pre;fir[x]=t;
for(rt i=F[x];i;i=N[i])if(a[i]!=pre){
deep[a[i]]=deep[x]+c[i];
dep[a[i]]=dep[x]+;
dfs(a[i],x);
size[x]+=size[a[i]];
q[++t]=x;
}
} void rebuild_init(int x,int pre){
for(rt i=F[x];i;i=N[i])if(a[i]!=pre){
e[x].push_back({a[i],c[i]});
rebuild_init(a[i],x);
}
}
void rebuild(){
clear();
for(rt i=;i<=n;i++){
if(e[i].size()<=)for(auto j:e[i])add(i,j.a,j.c*(j.a<=la)),add(j.a,i,j.c*(j.a<=la));
else {
int v1=++n,v2=++n;
add(i,v1,);add(v1,i,);add(i,v2,);add(v2,i,);
for(rt j=;j<e[i].size();j++)if(j&)e[v1].push_back(e[i][j]);
else e[v2].push_back(e[i][j]);
}
} }
int mins(int x,int y){return dep[x]<dep[y]?x:y; }
void LCA_init(){
for(rt i=;i<=t;i++)st[][i]=q[i];
for(rt i=;i<=;i++)
for(rt j=;j<=t;j++)
st[i][j]=mins(st[i-][j],st[i-][min(t,j+(<<i-))]);
for(rt i=;i<=t;i++)lg2[i]=lg2[i>>]+;
}
inline int LCA(const int x,const int y){
int L=fir[x],R=fir[y];if(L>R)swap(L,R);
const int len=lg2[R-L+];
return mins(st[len][L],st[len][R-(<<len)+]);
}
inline ll dis(const int x,const int y){
return deep[x]+deep[y]-deep[LCA(x,y)]*;
}
inline bool anc(const int x,const int y){//x是否为y祖先
return dfn[x]<=dfn[y]&&dfn[x]+size[x]->=dfn[y];
}
}T1,T2,T3,xs;
void build(int n,int *A){
xs.clear();//对于点集A在xs上建虚树
static int q[M],sta[M];int tott=n,topp=;
static bool vis[M];
for(rt i=;i<=n;i++)q[i]=A[i],vis[q[i]]=;
for(rt i=;i<=n;i++)sorttable[i]=T2.dfn[q[i]];
sort(q+,q+n+,cmp);
for(rt i=n;i>=;i--){
int lca=T2.LCA(q[i],q[i-]);
if(!vis[lca])vis[lca]=,q[++tott]=lca,col[lca]=;
}
for(rt i=;i<=tott;i++)sorttable[q[i]]=T2.dfn[q[i]];
sort(q+,q+tott+,cmp);
sta[topp=]=q[];
for(rt i=;i<=tott;i++){
while(topp&&!T2.anc(sta[topp],q[i]))topp--;
if(topp){
ll val=-T2.deep[sta[topp]]+T2.deep[q[i]];
xs.add(sta[topp],q[i],val);
}sta[++topp]=q[i];
}
for(rt i=;i<=tott;i++)vis[q[i]]=;
Root=q[];
} void printblack(int x,int pre,ll ds=){//黑1白2
if(x<=la)A[++sum]=x,col[x]=,dist[x]=ds;
for(rt i=T1.F[x];i;i=T1.N[i])if(T1.a[i]!=pre&&!vis[i>>])printblack(T1.a[i],x,ds+T1.c[i]);
}
void printwhite(int x,int pre,ll ds=){//黑1白2
if(x<=la)A[++sum]=x,col[x]=,dist[x]=ds;
for(rt i=T1.F[x];i;i=T1.N[i])if(T1.a[i]!=pre&&!vis[i>>])printwhite(T1.a[i],x,ds+T1.c[i]);
}
void get(int x,int pre){
sz[x]=;
for(rt i=T1.F[x];i;i=T1.N[i])if(T1.a[i]!=pre&&!vis[i>>]){
get(T1.a[i],x);
const int val=abs(all-*sz[T1.a[i]]);
if(val<nowmin)nowmin=val,ed=i;
sz[x]+=sz[T1.a[i]];
}
}
ll calc(int x,int y){//左黑右白
if(x==-||y==-)return -100000000000000ll;
return dist[x]+dist[y]+T2.deep[x]+T2.deep[y]+T3.dis(x,y);
}
struct white{int x,y;};
struct black{int x,y;};
ll calcw(white x){
return dist[x.x]+dist[x.y]+T2.deep[x.x]+T2.deep[x.y]+T3.dis(x.x,x.y);
}
ll calcb(black x){
return dist[x.x]+dist[x.y]+T2.deep[x.x]+T2.deep[x.y]+T3.dis(x.x,x.y);
}
white maxw(white x,white y){
if(x.x==-&&x.y==-)return y;
if(y.x==-&&y.y==-)return x;
if(x.x==-||x.y==-)return y;
if(y.x==-||y.y==-)return x;
if(calcw(x)>calcw(y))return x;else return y;
}
black maxb(black x,black y){
if(x.x==-&&x.y==-)return y;
if(y.x==-&&y.y==-)return x;
if(x.x==-||x.y==-)return y;
if(y.x==-||y.y==-)return x;
if(calcb(x)>calcb(y))return x;else return y;
}
inline white operator +(const white x,const white y){
return maxw(maxw(x,y),maxw(maxw(maxw((white){x.x,y.x},(white){x.x,y.y}),(white){x.y,y.x}),(white){x.y,y.y}));
}
inline black operator +(const black x,const black y){
return maxb(maxb(x,y),maxb(maxb(maxb((black){x.x,y.x},(black){x.x,y.y}),(black){x.y,y.x}),(black){x.y,y.y}));
}
inline ll Calc(const black x,const white y){
return max(max(max(calc(x.x,y.x),calc(x.x,y.y)),calc(x.y,y.x)),calc(x.y,y.y));
}
pair<black,white>DP(int x,ll val){
pair<black,white>ret={{-,-},{-,-}};
if(col[x]==)ret.first.x=x;
if(col[x]==)ret.second.x=x;
for(rt i=xs.F[x];i;i=xs.N[i]){
pair<black,white>la=DP(xs.a[i],val);
ll res=max(Calc(ret.first,la.second),Calc(la.first,ret.second))+val-2ll*T2.deep[x];
ans=max(ans,res);
ret.first=ret.first+la.first;
ret.second=ret.second+la.second;
}
return ret;
}
void solve(int x,int siz){
if(siz==)return;
nowmin=all=siz;
get(x,x);
int xx=T1.a[ed],yy=T1.a[ed^];vis[ed>>]=;int now=sz[xx];
sum=;printblack(xx,yy);printwhite(yy,xx);B=xx;W=yy;
build(sum,A);DP(Root,T1.c[ed]);
solve(xx,now);solve(yy,siz-now);
}
int main(){
n=read();la=n;
for(rt i=;i<n;i++){
x=read();y=read();ll z=read();
T1.add(x,y,z);
T1.add(y,x,z);
}
for(rt i=;i<n;i++){
x=read();y=read();ll z=read();
T2.add(x,y,z);
T2.add(y,x,z);
}
for(rt i=;i<n;i++){
x=read();y=read();ll z=read();
T3.add(x,y,z);
T3.add(y,x,z);
}
T1.rebuild_init(,);T1.rebuild();
T1.dfs(,);T1.LCA_init();T2.dfs(,);T2.LCA_init();T3.dfs(,);T3.LCA_init();
solve(,n);
cout<<ans;
return ;
}