#include<bits/stdc++.h>#defineTypeint#defineqr(x)x=read()usingnamespacestd;inlineTyperead(){ charc=getchar();Typex=0,f=1; while(!isdigit(c))(c=='-'?f=1:f=-1),c=getchar(); while(isdigit(c))x=(x<<1)+(x<<3)+

先考虑只有两颗树要咋做，柿子先变成\(dep_x+dep_y-2\timesdep_{lca}+dist_2(x,y)\)我们可以新建节点\(x'\rightarrowx\)，边权为\(dep_x\)，这样上面的式子可以看作枚举\(lca\)后，选出一个端点在不同子树中的直径，可以直接\(DP\)合并直径再考虑多了一颗树，我们可以进行边分治，枚

我们先将柿子变成\(\frac{1}{2}(dis_{x,y}+dep_{x}+dep_{y})-dep'_{lca'}\)考虑边分治，枚举断边，我们将一个点在第二棵树上的点权看成是\(v_x=d_x+dep_x\)，答案就为\(v_x+v_y+dep'_{lca'}\)对于每次边分治将分治联通块内所有点在第二棵树上的建出虚树，同时将分治联通块以分治中心

namespaceBFZ{ intk=1,ssz,rt,tot; inth[N],dep[N],sz[N],vis[N]; vector<pair<int,int>>G[N]; structAB{ inta,b,c,n; }d[N*2]; voidcun(intx,inty,intz){ d[++k]={x,y,z,h[x]},h[x]=k; } voidrebuild(intx,intfa){ inttmp=0,lst=0