锟题x2

以下用$a\rightarrow b$表示端点为$a,b$的链

把式子写成$(h_1(x)+h_1(y)-h_1(lca))-h_2(lca')$，第一部分就是$x\rightarrow rt$和$y\rightarrow rt$的并的总长

考虑对第一棵树边分治，假设分治到$(u,v)$，我们想要统计所有跨过$(u,v)$的$x\rightarrow y$

设在树$1$上$fa_v=u$，对于$u$这边的点$x$，令$f_x=-\infty,g_x=dis(x,u\rightarrow rt)$，对$v$这边的点$y$，令$f_y=h_1(y),g_y=-\infty$，那么$h_1(x)+h_1(y)-h_1(lca)=g_x+f_y$（将另外的$f,g$设为$-\infty$是为了防止统计到不跨过$(u,v)$的情况）

所以我们可以将当前分治范围内的点拿出来在树$2$上建虚树，在虚树上统计答案即可

最后不要忘了统计$x=y$的答案...

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int inf=2147483647;const ll linf=922337203685477580ll;int n;struct pr{	int to,v;	pr(int a=0,int b=0){to=a;v=b;}};struct tree1{	int h[733340],nex[1466670],to[1466670],v[1466670],M;	vector
        
         g[366670];	void ins(int a,int b,int c){		M++;		to[M]=b;		v[M]=c;		nex[M]=h[a];		h[a]=M;	}	void add(int a,int b,int c){		ins(a,b,c);		ins(b,a,c);	}	int N;	void dfs(int fa,int x){		vector
         
          ::iterator it;		int 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);		}	}	ll dis[733340];	int fa[733340],dep[733340];	void dfs(int 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;				dis[to[i]]=dis[x]+v[i];				dfs(to[i]);			}		}	}	void gao(){		int i,x,y,z;		for(i=1;i
          
           dfn[y])swap(x,y); return query(dfn[x],dfn[y]); } void gao(){ int i,j,x,y,z; for(i=1;i
           
            >1]+1; }}t2;bool cmp(int x,int y){return t2.dfn[x]
            
             1&&t2.dep[st[tp-1]]>t2.dep[l]){ vt.add(st[tp-1],st[tp]); tp--; } if(t2.dep[st[tp]]>t2.dep[l]){ vt.add(l,st[tp]); tp--; } if(t2.dep[st[tp]]
             
              t1.dep[y])swap(x,y); build(); vt.clear(st[1]); dfs3(0,x,0); dfs4(0,y); vt.dfs(st[1]); solve(x); solve(y);}int main(){ scanf("%d",&n); t1.gao(); t2.gao(); ans=-linf; solve(1); for(int i=1;i<=n;i++)ans=max(ans,t1.dis[i]-t2.dis[i]); printf("%lld",ans);}