点一下，写一年！A到就是赚到！
一个自然的思路是枚举$\textrm{LCA}^\prime(x,y)$，这样$x$和$y$在$T^\prime$上分属$\textrm{LCA}^\prime(x,y)$的不同子树，剩下在$T$上的部分可以写成$f(x,y)=\frac{1}{2}(\textrm{depth}(x)+\textrm{depth}(y)+\textrm{dis}(x,y))$，可以做类似dsu on a tree的过程来统计答案. 那么我们需要一个数据结构维护一个点集$S$，支持对一个点$u$查询$\min _{v \in S}f(u,v)$以及向$S$中插入一个点.
像这样维护树上点集，查询权值在边上的信息的时候，可以考虑使用边分治，先对树$T$建立起一棵边分树，把点集$S$按照该分治结构划分，形成一棵有$O(|S|)$个点的树结构，每个点保存$\max\textrm{depth}(u)+\textrm{dis}(u,v)$，其中$u$为该点代表的分治结构里面的关键点，$v$为上一层分治结构的分治边靠近当前分治结构的端点. 那么查询直接在这棵树上面往下走就可以了，插入也可以很容易地处理. 这样我们就可以$\mathcal O(n\log^2 n)$地解决这道题.
事实上还可以进一步优化，注意到边分树是二叉树结构，可以直接使用类似线段树合并的算法，并顺便计算贡献，而不需要进行启发式合并，这样的复杂度是$\mathcal O(n\log n)$.
边分树是二叉树结构，所以很多东西想起来会更加方便. 但是边分树常数相对会更大，而且如果询问的信息在点上，就不能加入辅助点，复杂度会退化到$\mathcal O(n^2)$. 刚刚那些东西用点分树理论上可能也是可以做到的，但是会麻烦很多.
不知道为什么还需要辛辛苦苦卡内存……
截止到写这篇题解的时候，loj上有若干份AC代码可以对拍出一堆错. 等待数据加强.
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
using namespace std;
const ll INF=1e18;
template<class T>struct mempool{
T *s,*t;
mempool():s(NULL),t(NULL){}
inline T* alloc(){
return s==t && (t=(s=new T[K])+K),s++;
}
};
struct edge{
ele v,w;
bool flag;
edge *nxt,*rev;
}ep[maxn<<2],*ecnt;
struct node{
edge *e;
ll mx;
node *l,*r;
};
ele n,acnt,size[maxn],w[maxn];
ll ans,dep[maxn];
edge *h[maxn],*g[maxn],*h1[maxn];
mempool<node> np;
vector<ll> vd[maxn];
vector<bool> vc[maxn];
node *T[maxn],*er;
inline void boom(){
char *c=NULL; putchar(*c);
}
inline void addedge1(edge *h[],ele u,ele v,ele w){
edge *p=ecnt++;
p->v=v; p->w=w; p->flag=false; p->nxt=h[u];
p->rev=ep+((ecnt-ep-1)^1);
h[u]=p;
}
inline void addedge(edge *h[],ele u,ele v,ele w){
addedge1(h,u,v,w); addedge1(h,v,u,w);
}
void dfs1(ele p,ele i){
ele tmp=i;
for (edge *j=h[i]; j; j=j->nxt)
if (j->v!=p){
addedge(h1,tmp,acnt,0);
addedge(h1,acnt,j->v,j->w);
tmp=acnt++;
dfs1(i,j->v);
}
}
void dfs2(ele p,ele i){
size[i]=1;
for (edge *j=h1[i]; j; j=j->nxt)
if (j->v!=p && !j->flag){
dfs2(i,j->v);
size[i]+=size[j->v];
}
}
edge* dfs3(ele p,ele i,ele s){
edge *ans=NULL; w[i]=max(size[i],s-size[i]);
for (edge *j=h1[i]; j; j=j->nxt)
if (j->v!=p && !j->flag){
edge *tmp=dfs3(i,j->v,s);
if (!ans || (tmp && w[tmp->v]<w[ans->v])) ans=tmp;
if (!ans || w[j->v]<w[ans->v]) ans=j;
}
return ans;
}
void dfs5(ele p,ele i,ll d,ele c){
if (i<n) vd[i].push_back(d),vc[i].push_back(c);
for (edge *j=h1[i]; j; j=j->nxt)
if (j->v!=p && !j->flag) dfs5(i,j->v,d+j->w,c);
}
node* build(ele i){
dfs2(-1,i);
edge *k=dfs3(-1,i,size[i]);
if (!k) return NULL;
k->flag=k->rev->flag=true;
dfs5(-1,k->rev->v,0,0); dfs5(-1,k->v,0,1);
node *p=np.alloc(); p->e=k;
p->l=build(k->rev->v);
p->r=build(k->v);
return p;
}
void dfs4(ele p,ele i){
for (edge *j=h1[i]; j; j=j->nxt)
if (j->v!=p) dep[j->v]=dep[i]+j->w,dfs4(i,j->v);
}
inline void maintain(node *x){
x->mx=0;
if (x->l) x->mx=max(x->mx,x->l->mx);
if (x->r) x->mx=max(x->mx,x->r->mx);
}
node* build(node *x,ele i,ele j){
node *p=np.alloc();
p->l=p->r=NULL;
if (!x) return p;
p->e=x->e;
if (!vc[i][j]){
p->l=build(x->l,i,j+1);
p->l->mx=vd[i][j]+dep[i];
}
else{
p->r=build(x->r,i,j+1);
p->r->mx=vd[i][j]+dep[i];
}
return p;
}
node* merge(node *a,node *b,ll&ans){
if (!a) return b;
if (!b) return a;
if (a->l && b->r) ans=max(ans,a->l->mx+b->r->mx+a->e->w);
if (a->r && b->l) ans=max(ans,a->r->mx+b->l->mx+a->e->w);
a->l=merge(a->l,b->l,ans);
a->r=merge(a->r,b->r,ans);
a->mx=max(a->mx,b->mx);
return a;
}
void dfs6(ele p,ele i,ll d){
ans=max(ans,dep[i]-d);
T[i]=build(er,i,0);
for (edge *j=g[i]; j; j=j->nxt)
if (j->v!=p){
dfs6(i,j->v,d+j->w);
ll tmp=-INF;
T[i]=merge(T[i],T[j->v],tmp);
if (tmp>-INF) ans=max(ans,tmp/2-d);
}
}
int main(){
scanf("%d",&n);
ecnt=ep; memset(h,0,sizeof(h));
for (int i=0; i<n-1; ++i){
ele u,v,w;
scanf("%d%d%d",&u,&v,&w); --u,--v;
addedge(h,u,v,w);
}
memset(g,0,sizeof(g));
for (int i=0; i<n-1; ++i){
ele u,v,w;
scanf("%d%d%d",&u,&v,&w); --u,--v;
addedge(g,u,v,w);
}
acnt=n;
memset(h1,0,sizeof(h1));
dfs1(-1,0);
// memcpy(h1,h,sizeof(h));
er=build(0);
dep[0]=0;
dfs4(-1,0);
ans=-INF;
dfs6(-1,0,0);
printf("%lld\n",ans);
// while(1);
return 0;
}