锟题x1

以下用$d_k(x,y)$表示$x,y$在第树$k$上的距离，$h_k(x)$表示$x$在树$k$上的深度

先做两棵树，即最大化$d_1(x,y)+d_2(x,y)=h_1(x)+h_1(y)-2h_1(lca)+d_2(x,y)$，其中$lca$是$x,y$在树$1$上的lca

考虑在树$1$上枚举$lca$，即是要最大化$h_1(x)+h_2(y)+d_2(x,y)$，于是我们可以对每个树$2$的点$i$建多一条边$(i,i',h_1(i))$，在dfs树$1$的同时维护（树$1$的子树中的每个$x$对应到树$2$的$x'$这些点在树$2$中的直径）即可

现在有了树$3$，考虑对其边分治，设分治到$(u,v)$，我们要查询在树$3$上跨过$(u,v)$的答案，这其实就是在两棵树的基础上加了$d_3(x,u)+d_3(y,v)+w_{u,v}$还有路径$(x,y)$必须经过$(u,v)$的约束，那么将当前分治范围内的点拿出来在树$1$上建虚树，并给$(u,v)$两边的点染不同的颜色，于是接下来我们维护不同颜色的直径，之后就和两棵树完全一样了

最后的一个小问题就是边分治的复杂度，这里直接多叉转二叉即可（对每个点新建一条$0$链）

说起来很简单，但写起来还是挺长的

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;const int inf=2147483647;int n;struct tree1{	int h[100010],nex[200010],to[200010],M;	ll v[200010];	void add(int a,int b,ll c){		M++;		to[M]=b;		v[M]=c;		nex[M]=h[a];		h[a]=M;	}	int fa[100010],dfn[100010],mn[200010][18],dep[200010],lg[200010];	ll d[100010];	void dfs(int x){		dfn[x]=++M;		mn[M][0]=x;		dep[x]=dep[fa[x]]+1;		for(int i=h[x];i;i=nex[i]){			if(to[i]!=fa[x]){				fa[to[i]]=x;				d[to[i]]=d[x]+v[i];				dfs(to[i]);				mn[++M][0]=x;			}		}	}	int qmin(int x,int y){return dep[x]
         
          dfn[y])swap(x,y);		return query(dfn[x],dfn[y]);	}	void gao(){		int i,j,x,y;		ll z;		for(i=1;i
          
           >1]+1; }}t1;struct tree2{ int h[100010],nex[200010],to[200010],M; ll v[200010]; void add(int a,int b,ll c){ M++; to[M]=b; v[M]=c; nex[M]=h[a]; h[a]=M; } int fa[100010],lg[200010],in[100010]; ll d[100010],mn[200010][19]; void dfs(int x){ in[x]=++M; mn[M][0]=d[x]; for(int i=h[x];i;i=nex[i]){ if(to[i]!=fa[x]){ fa[to[i]]=x; d[to[i]]=d[x]+v[i]; dfs(to[i]); mn[++M][0]=d[x]; } } } ll query(int l,int r){ int k=lg[r-l+1]; return min(mn[l][k],mn[r-(1<
           
            in[y])swap(x,y); return d[x]+d[y]-2*query(in[x],in[y]); } void gao(){ int i,j,x,y; ll z; for(i=1;i
            
             >1]+1; }}t2;struct pr{ int to; ll v; pr(int a=0,ll b=0){to=a;v=b;}};struct tree3{ int h[200010],nex[400010],to[400010],M; ll v[400010]; void ins(int a,int b,ll c){ M++; to[M]=b; v[M]=c; nex[M]=h[a]; h[a]=M; } void add(int a,int b,ll c){ ins(a,b,c); ins(b,a,c); } vector
             
              g[100010]; int N; void dfs(int fa,int x){ int p; vector
              
               ::iterator it; if(g[x].size()){ p=0; for(it=g[x].begin();it!=g[x].end();it++){ if(it->to!=fa){ if(p){ N++; add(p,N,0); add(N,it->to,it->v); p=N; }else{ add(x,it->to,it->v); p=x; } } } } for(it=g[x].begin();it!=g[x].end();it++){ if(it->to!=fa)dfs(x,it->to); } } void gao(){ int i,x,y; ll z; for(i=1;i
               
                mx){\ x=u;\ y=v;\ mx=t;\ } ch(a.x,a.y) ch(b.x,b.y) ch(a.x,b.x) ch(a.x,b.y) ch(a.y,b.x) ch(a.y,b.y) return dia(x,y);}struct pd{ dia x,y; pd(dia a=0,dia b=0){x=a;y=b;} dia&operator[](int k){return k?x:y;}};pd operator+(pd a,pd b){return pd(a.x+b.x,a.y+b.y);}ll max(pd a,pd b){return max(max(a.x,b.y),max(a.y,b.x));}ll ans;bool vis[400010];int siz[200010],p[200010],M;void dfs1(int fa,int x){ if(x<=n)p[++M]=x; siz[x]=1; for(int i=t3.h[x];i;i=t3.nex[i]){ if(!vis[i]&&t3.to[i]!=fa){ dfs1(x,t3.to[i]); siz[x]+=siz[t3.to[i]]; } }}int al,mn,cn;void dfs2(int fa,int x){ for(int i=t3.h[x];i;i=t3.nex[i]){ if(!vis[i]&&t3.to[i]!=fa){ dfs2(x,t3.to[i]); if(abs(al-2*siz[t3.to[i]])
                
                 1&&t1.dep[st[tp-1]]>t1.dep[l]){ vt.add(st[tp-1],st[tp]); tp--; } if(t1.dep[st[tp]]>t1.dep[l]){ vt.add(l,st[tp]); tp--; } if(t1.dep[st[tp]]