题目描述

题解

首先来看这个我们要最大化的东西。

deep[u]+deep[v]-deep[lca(u,v)]-deep[lca(u',v')]

后面的那个东西看起来不太合群，我们可以把前后拆开。

deep[u]+deep[v]-deep[lca(u,v)]

我们发现这其实就是u到根的链和v到根的链的并。

然后它还等于(deep[u]+deep[v]+dis[u][v])/2

因为deep数组我们可以直接求出，所以我们就把一颗有根树上的问题放到了无根树上，也就是可以去掉lca的影响了。

然后考虑枚举第二颗树的LCA,那么一组合法的点应当在这个点的两颗不同的子树中。

然后对第一棵树边分，发现这颗边分树也是一颗二叉树，每个叶子结点代表原树上的一个点。

于是这题的做法来了，我们在dfs第二颗树的时候，像线段树合并一样合并边分树，因为不管叶子的情况下，每个节点都代表一条边，每条边连接着两个点。

这样我们对这个点记一个lans和rans分别代表左端点的最优答案和右端点的最优答案。

维护答案的形式为deep[x]+dis(x,edge)

合并的时候顺带计算答案。

注意，要考虑u和v重合的情况。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #define inf 1e18#define N 740009using namespace std;typedef long long ll;ll lans[N*23],rans[N*23],ans,dis[N],deep[N][20],nowdeep,val[N*5];int atp,size[N],sum,nowroot,root,ha,finaldep[N];int fa[N*5],ls[N*5],rs[N*5],tr[N*23][2],dian,T[N],n,id[N*23];bool jin[N<<1];inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct tu{    int head[N],tot;    struct edge{
   int n,to;ll l;}e[N<<1];    void clear(){memset(head,0,sizeof(head));tot=0;}     inline void add(int u,int v,ll l){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;}}E[2];struct node{
   int n,to;ll l;}e[N<<2];int head[N<<1],tot=1;inline void add(int u,int v,ll l){   e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;   e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=l;}void dfs1(int u,int fa){    int now=0;    for(int i=E[0].head[u];i;i=E[0].e[i].n)if(E[0].e[i].to!=fa){        int v=E[0].e[i].to;dis[v]=dis[u]+E[0].e[i].l;        if(!now){add(u,v,E[0].e[i].l);now=u;}        else{++atp;add(now,atp,0);add(atp,v,E[0].e[i].l);now=atp;}        dfs1(v,u);    }}void getroot(int u,int fa){    size[u]=1;    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!jin[i]){        int v=e[i].to;        getroot(v,u);        size[u]+=size[v];        if(max(size[v],sum-size[v])