三棵树真的能让人自闭

第一棵树常规做法，直接边分治，处理出每个点到分治边的距离\(dis_i\)，同时黑白染色

第二棵树还是常规做法，直接建虚树，处理出每个点到根的路径和\(pre_i\)

要是两个树我们现在树形\(dp\)直接就做了，但是还有第三棵树，我们规定第三棵树上点的点权\(val_i=dis_i+pre_i\)，现在的问题转化为对于虚树上的每个节点，从其子树里找两个颜色不同的点，使得这两个点在第三棵树上距离(边权+端点点权)最大

看起来比较令人自闭，但是我们注意到一个重要的条件，边权都为正，也就是说对于树上每一个点，距离其最远的点一定是树直径的端点

于是利用这个性质，我们只需要维护同色点形成的直径就好了，异色点取最大值我们直接两条直径四个端点取一下就好了；同色直径直接合并就好了，新的直径的端点只可能是原来的四个端点中的两个，共\(C_4^2=6\)种，大力讨论就好了

使用分裂排序和\(O(1)LCA\)可以使得复杂度变为\(O(nlogn)\)

代码，生涯无展开最长代码226行

#include
    
     #define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline LL read() {    char c=getchar();LL x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3ll)+(x<<1ll)+c-48,c=getchar();return x;}const int maxn=1e5+5;const int M=maxn*4;std::vector
     
       son[M];std::vector
      
        v[M];struct E{int v,nxt;LL w;}e[M<<1];int head[M],vis[M],sum[M],Mnow,dfn[maxn];int c[2][maxn],tp[2],col[maxn],b[maxn];LL val[maxn],ans;struct Route{int x,y;LL v;}dp[maxn][2];int u[maxn][2],rl[maxn];int n,rn,rt,num,S;inline void add(int x,int y,LL w) {    e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=w;}void dfs1(int x,int fa) {    for(re int i=head[x];i;i=e[i].nxt) {        if(e[i].v==fa) continue;        son[x].push_back(e[i].v),v[x].push_back(e[i].w);        dfs1(e[i].v,x);    }}inline int cmp(int A,int B) {return dfn[A]
       
        y) std::swap(x,y);        int k=lg[y-x+1];        if(deep[f[k][x]]
        
         <
         
          >1]+1; for(re int j=1;j<=lg[tot];j++) for(re int i=1;i+(1<<(j-1))<=tot;i++) if(deep[f[j-1][i]]
          
           <<(j-1))]]) f[j][i]=f[j-1][i]; else f[j][i]=f[j-1][i+(1<<(j-1))]; }}T3;inline LL get(Route A,Route B) { LL t1=T3.dis(A.x,B.y),t2=T3.dis(A.y,B.x); LL t3=T3.dis(A.x,B.x),t4=T3.dis(A.y,B.y); return max(max(t1,t2),max(t3,t4));}inline Route merge(Route A,Route B) { int x,y;LL v,t; if(A.v>B.v) x=A.x,y=A.y,v=A.v; else x=B.x,y=B.y,v=B.v; t=T3.dis(A.x,B.y); if(t>v) x=A.x,y=B.y,v=t; t=T3.dis(A.x,B.x); if(t>v) x=A.x,y=B.x,v=t; t=T3.dis(A.y,B.y); if(t>v) x=A.y,y=B.y,v=t; t=T3.dis(A.y,B.x); if(t>v) x=A.y,y=B.x,v=t; return (Route){x,y,v};}struct Virual_Tree { struct E{int v,nxt;LL w;}e[maxn<<1]; int head[maxn],lg[maxn<<1],f[18][maxn<<1],pos[maxn]; LL pre[maxn];int deep[maxn],top,st[maxn]; int num,tot,cnt; inline int LCA(int x,int y) { x=pos[x],y=pos[y]; if(x>y) std::swap(x,y); int k=lg[y-x+1]; if(deep[f[k][x]]
           
            <
            
             1&&dfn[st[top-1]]>=dfn[lca]) add(st[top-1],st[top],0),top--; if(lca!=st[top]) add(lca,st[top],0),st[top]=lca; st[++top]=x; } inline void build() { LL w;int x,y; for(re int i=1;i
             
              >1]+1; for(re int j=1;j<=lg[tot];j++) for(re int i=1;i+(1<<(j-1))<=tot;i++) if(deep[f[j-1][i]]
              
               <<(j-1))]]) f[j][i]=f[j-1][i]; else f[j][i]=f[j-1][i+(1<<(j-1))]; for(re int i=1;i<=rn;i++) b[i]=i; std::sort(b+1,b+rn+1,cmp); } inline void get_tree(int l,int r) { num=0;top=0; if(b[l]!=1) ins(1); for(re int i=l;i<=r;i++) val[b[i]]+=pre[b[i]],ins(b[i]),rl[b[i]]=1; while(top>1) add(st[top-1],st[top],0),top--; } void tree_dp(int x) { if(rl[x]) { u[x][col[x]]=1; dp[x][col[x]].x=dp[x][col[x]].y=x; dp[x][col[x]].v=0; } for(re int i=head[x];i;i=e[i].nxt) { tree_dp(e[i].v);LL t; if(u[e[i].v][0]&&u[x][1]) t=get(dp[x][1],dp[e[i].v][0]),ans=max(ans,t-2ll*pre[x]); if(u[e[i].v][1]&&u[x][0]) t=get(dp[x][0],dp[e[i].v][1]),ans=max(ans,t-2ll*pre[x]); if(u[e[i].v][0]) { if(!u[x][0]) dp[x][0]=dp[e[i].v][0]; else dp[x][0]=merge(dp[x][0],dp[e[i].v][0]); u[x][0]=1; } if(u[e[i].v][1]) { if(!u[x][1]) dp[x][1]=dp[e[i].v][1]; else dp[x][1]=merge(dp[x][1],dp[e[i].v][1]); u[x][1]=1; } } } void del(int x) { for(re int i=head[x];i;i=e[i].nxt) del(e[i].v); head[x]=val[x]=0;u[x][0]=u[x][1]=0,rl[x]=0; }}T2;void getrt(int x,int fa) { sum[x]=1; for(re int i=head[x];i;i=e[i].nxt) { if(vis[i>>1]||e[i].v==fa) continue; getrt(e[i].v,x);sum[x]+=sum[e[i].v]; int now=max(sum[e[i].v],S-sum[e[i].v]); if(now
               
                >1]||e[i].v==fa) continue; dfs2(e[i].v,x,o,d+e[i].w); }}void solve(int x,int s,int l,int r) { if(l>r) return; Mnow=M,S=s,getrt(x,0); if(Mnow==M) return;vis[rt>>1]=1; dfs2(e[rt].v,0,0,e[rt].w),dfs2(e[rt^1].v,0,1,0); T2.get_tree(l,r); T2.tree_dp(1); tp[0]=tp[1]=0;T2.del(1); for(re int i=l;i<=r;i++) c[col[b[i]]][++tp[col[b[i]]]]=b[i]; for(re int i=l,k=1;k<=tp[0];i++,k++) b[i]=c[0][k]; for(re int i=l+tp[0],k=1;k<=tp[1];i++,k++) b[i]=c[1][k]; int now=s-sum[e[rt].v],k=rt,L=l+tp[0]-1,R=r-tp[1]+1; solve(e[k].v,sum[e[k].v],l,L); solve(e[k^1].v,now,R,r);}int main() { rn=n=read();LL w;int s[2]; for(re int x,y,i=1;i