【题解】「CTSC2018」暴力写挂 边分治 + 虚树 — Qiuly

考虑边分治。

边分治的时候考虑跨过中心边的点对 $(x,y)$ 的答案。考虑到 $d_x+d_y-d_{lca(x,y)}$ 其实是 $\frac{1}{2}(dix(x,y)+d_x+d_y)$ ，这下就跟 $lca$ 没关系了。 显然在边分治的过程中 $dis(x,y)$ 也可以被拆开，令 $p_x$ 表示 $x$ 到边分治中所属子树的根的距离，显然 $dix(x,y)=p_x+p_y+1$ 。

这样的话一个点 $x$ 的权值就是 $d_x+p_x$ 。接下来后面那个 $d’_{lca'(x,y)}$ 怎么办？

考虑对当前边分治范围内所有点，在第二棵树上建立虚树。建立虚树后考虑每个点作为 $lca'(x,y)$ 的答案即可。这点可以简单树形 DP 解决。

注意到一共分治 $\log$ 层，每层的所有分治块节点数之和不超过 $n$ ，虚树点数是 $O(k)$ 的（$k$ 为关键点数），因此时间复杂度是 $O(n\log n)$ 的。

然后就做完了，注意到边分治的点数上界是 $4n$ ，这下子点数就变成了 $10^6$ 级别，需要注意实现。注意到建虚树的时候需要求 $lca$ 并且需要将所有关键点按照 $dfn$ 序排序，$O(1)$ 的 $lca$ 很容易实现，排序的话归并边分治的两个儿子即可。

const int N=1.5e6+5;
const int LogN=22;

int n,lstn;
ll ans,dison1[N];

int cnt=1,head[N];
std::vector <pii> G2[N];
struct Edge {int nxt,to,val;} G1[N<<1];

inline void addedge(int u,int v,int w) {
    G1[++cnt]=(Edge){head[u],v,w},head[u]=cnt;
}

// {{{ Tree2 - virtual tree

ll dis[N],god[N];
int top,sta[N],tag[N];
int m,tim,extraval,in[N],dep[N],dfn[N],_log[N],st[N][LogN];
std::vector <int> Gv[N];

void getdfn(int u,int lst) {
    dfn[u]=++tim,dep[u]=dep[lst]+1,st[in[u]=++m][0]=u;
    for(pii v:G2[u]) if(v.fi!=lst) dis[v.fi]=dis[u]+v.se,getdfn(v.fi,u),st[++m][0]=u;
}

#define chkgod(x,y) (dep[x]<dep[y]?x:y)
inline void init() {
    getdfn(1,0),_log[0]=-1;
    lep(j,1,21) { int t=1<<j,k=t>>1; lep(i,1,m) if(i+t-1<=m) {
        st[i][j]=chkgod(st[i][j-1],st[i+k][j-1]);
    }}
    lep(i,1,m) _log[i]=_log[i>>1]+1;
}
inline int lca(int x,int y) {
    x=in[x],y=in[y]; if(x>y) swap(x,y); int k=_log[y-x+1];
    return chkgod(st[x][k],st[y-(1<<k)+1][k]);
}

void clear(int u) {
    for(int v:Gv[u]) clear(v);
    Gv[u].clear(),tag[u]=0,god[u]=0;
}
void build(std::vector <int> p) {
    sta[top=1]=1; for(int u,i=p.size()-1;~i;--i) if(u=p[i],u!=1) {
        int l=lca(u,sta[top]);
        if(l!=sta[top]) {
            while(dfn[l]<dfn[sta[top-1]]) Gv[sta[top-1]].pb(sta[top]),--top;
            if(dfn[l]!=dfn[sta[top-1]]) Gv[l].pb(sta[top]),sta[top]=l;
            else Gv[l].pb(sta[top--]);
        }
        sta[++top]=u;
    }
    lep(i,2,top) Gv[sta[i-1]].pb(sta[i]);
}
std::pair <ll,ll> update(int u) {
    ll max1=-1e18,max2=-1e18;
    if(tag[u]==1) max1=god[u]; if(tag[u]==2) max2=god[u];
    for(int v:Gv[u]) {
        std::pair <ll,ll> now=update(v);
        chkmax(ans,(max1+now.se+extraval)/2-dis[u]),chkmax(max1,now.fi),
        chkmax(ans,(max2+now.fi+extraval)/2-dis[u]),chkmax(max2,now.se);
    }
    return mkp(max1,max2);
}

// }}}

// {{{ Tree1 - Edge divide

int rt,nowmax,vis[N],siz[N];

// {{{ Rebuild

void getson(int u,int lst) {
    for(int v,i=head[u];i;i=G1[i].nxt) if(v=G1[i].to,v!=lst)
        dison1[v]=dison1[u]+G1[i].val,G2[u].pb(mkp(v,G1[i].val)),getson(v,u);
}
void rebuild() {
    getson(1,0); lep(i,1,n) head[i]=0; cnt=1; lep(i,1,n) {
        int now=G2[i].size()-1;
        if(now>1) {
            ++n,addedge(i,n,0),addedge(n,i,0);
            ++n,addedge(i,n,0),addedge(n,i,0);
            for(int j=0;j<=now;++j) (j&1)?G2[n].pb(G2[i][j]):G2[n-1].pb(G2[i][j]);
        } else for(pii j:G2[i]) addedge(i,j.fi,j.se),addedge(j.fi,i,j.se);
    }
    lep(i,1,n) G2[i].clear();
}
void check(int u,int lst) {
    for(int v,i=head[u];i;i=G1[i].nxt) if(v=G1[i].to,v!=lst) check(v,u);
}

// }}}

// {{{ Solve

void getrt(int u,int lst,int allsiz) {
    siz[u]=1;
    for(int v,i=head[u];i;i=G1[i].nxt) if(v=G1[i].to,v!=lst&&!vis[i>>1]) {
        getrt(v,u,allsiz),siz[u]+=siz[v];
        int tmpmax=max(siz[v],allsiz-siz[v]);
        if(tmpmax<nowmax) nowmax=tmpmax,rt=i;
    }
}
std::vector <std::pair <int,ll> > nodedis[N<<1]; void getdis(int u,int lst,ll len) {
    if(u<=lstn) nodedis[rt].pb(mkp(u,len));
    for(int v,i=head[u];i;i=G1[i].nxt) if(v=G1[i].to,v!=lst&&!vis[i>>1]) getdis(v,u,len+G1[i].val);
}

std::vector <int> solve(int u,int allsiz) {
    std::vector <int> node(0);

    nowmax=inf,getrt(u,0,allsiz);
    if(nowmax==inf) return (u>lstn?void():node.pb(u)),node;
    vis[rt>>1]=true; int now=rt,nxt=siz[G1[rt].to],p1=G1[now].to,p2=G1[now^1].to;

    // get dis
    getdis(p1,p2,0),getdis(p2,p1,0);

    // get son's answer
    std::vector <int> son1=solve(G1[now].to,nxt);
    std::vector <int> son2=solve(G1[now^1].to,allsiz-nxt);
    for(int v:son1) tag[v]=1; for(int v:son2) tag[v]=2;

    // merge
    while(son1.size()&&son2.size()) (dfn[son1.back()]<dfn[son2.back()])?
        (node.pb(son1.back()),son1.pp()):(node.pb(son2.back()),son2.pp());
    while(son1.size()) node.pb(son1.back()),son1.pp();
    while(son2.size()) node.pb(son2.back()),son2.pp();
    std::reverse(node.begin(),node.end());

    // build virtual tree to get answer 
    extraval=G1[now].val,build(node);
    for(auto ele:nodedis[now]) god[ele.fi]=ele.se+dison1[ele.fi];
    update(1),clear(1);

    // the end
    return node;
}

// }}}

// }}}

int u,v,w; int main() {
    IN(n),lstn=n;
    lep(i,2,n) IN(u,v,w),addedge(u,v,w),addedge(v,u,w);
    rebuild(),check(1,0);
    lep(i,2,lstn) IN(u,v,w),G2[u].pb(mkp(v,w)),G2[v].pb(mkp(u,w));
    init(),ans=-1e18,solve(1,n);
    lep(i,1,n) chkmax(ans,dison1[i]-dis[i]);
    printf("%lld\n",ans);
    return 0;
}