[CTSC2018]暴力写挂

Time_tears · 2021-05-28 21:32:01 · 题解

似乎基本没有边分治+虚树的做法？

定义 dis_k(x, y) 表示点对 (x, y) 在第 k 棵树上的距离。 则原“距离”式可以转化为：\dfrac{1}{2}dis_1(x,y)+\dfrac{1}{2}depth_1(x)+\dfrac{1}{2}depth_1(y)-depth_2(LCA_2(x,y))

如果边权均非负，那么最远点对信息可以合并，我们可以采用类似于通道这一题中的方法来解决。但是这里边权可能为负数。

我们可以对第一棵树进行边分治假设第一棵树上节点 x 到当前分治中心的距离为 D(x)，则原式可以进一步转化为

直接在第二棵树上建出虚树，然后在树上 DFS，并记录子树内节点在边分治中不同子树中 depth_1(x) + D(x) 的最大值，记为 f_1(x),f_2(x)，这样在合并子树的时候用 f_1(x)+f_2(y) 和 f_2(x)+f_1(y) 更新答案即可（其实就是求直径的另一种方法）。

复杂度瓶颈在于建虚树前的排序而这一部分可以用在通道一题中使用的归并方式快速解决，复杂度 O(n\log n)。

代码挺模块化的，就是跑得太慢了。。。

#include<bits/stdc++.h>
#define N 800005
#define ll long long
using namespace std;
const ll inf=1ll<<61;
int n,Log[N],is[N];ll W[N],ans=-inf;
inline int read() {
    int s=0,f=0;
    char ch=getchar();
    while(ch<48||ch>57)f|=(ch=='-'),ch=getchar();
    while(ch>47&&ch<58)s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return f?-s:s;
}
namespace T2 {
    int h[N],cnt,nx[N<<1],to[N<<1],vl[N<<1],s[N];
    int dfn[N],in[N],tot,t2,fp[N<<1],dep[N],top;
    ll dis[N],f1[N],f2[N];vector<int>g[N];
    struct node {
        int dep,x;
        node(int D=0,int X=0){dep=D,x=X;}
        bool operator<(node a) const {return dep<a.dep;}
    } rmq[20][N];
    void Addedge(int x,int y,int z) {nx[++cnt]=h[x],to[h[x]=cnt]=y,vl[cnt]=z,nx[++cnt]=h[y],to[h[y]=cnt]=x,vl[cnt]=z;}
    void Dfs(int x,int fa) {
        dfn[x]=++tot,dep[x]=dep[fa]+1,fp[in[x]=++t2]=x;
        for(int i=h[x],y; i; i=nx[i])if((y=to[i])!=fa)dis[y]=dis[x]+vl[i],Dfs(y,x),fp[++t2]=x;
    }
    void Pre() {
        for(int i=1; i<=t2; ++i)rmq[0][i]=node(dep[fp[i]],fp[i]);
        for(int j=1; (1<<j)<=t2; ++j)for(int i=1; i+(1<<j)<=t2+1; ++i)rmq[j][i]=min(rmq[j-1][i],rmq[j-1][i+(1<<j-1)]);
    }
    int Lca(int x,int y) {
        if(in[x]<in[y])swap(x,y);int len=Log[in[x]-in[y]+1];
        return min(rmq[len][in[y]],rmq[len][in[x]-(1<<len)+1]).x;
    }
    void Calc(int x) {
        if(is[x]==1)f1[x]=max(f1[x],W[x]);if(is[x]==0)f2[x]=max(f2[x],W[x]);
        for(int y:g[x]) {
            Calc(y),ans=max(ans,(max(f1[x]+f2[y],f2[x]+f1[y])>>1)-dis[x]);
            f1[x]=max(f1[x],f1[y]),f2[x]=max(f2[x],f2[y]);
        }
    }
    void Clear(int x) {f1[x]=f2[x]=-inf;for(int y:g[x])Clear(y);is[x]=-1,g[x].clear();}
    void Solve(vector<int>&p) {
        s[top=1]=1;
        for(int x:p) {
            int lca=Lca(s[top],x);
            if(lca==s[top])((x!=s[top])?s[++top]=x:0);
            else {
                while(dep[s[top-1]]>dep[lca])g[s[top-1]].push_back(s[top]),--top;
                if(g[lca].push_back(s[top--]),s[top]!=lca)s[++top]=lca;if(s[top]!=x)s[++top]=x;
            }
        }
        while(top>1)g[s[top-1]].push_back(s[top]),--top;Calc(1),Clear(1);
    }
}
namespace T1 {
    int h[N],cnt=1,nx[N<<1],to[N<<1],vl[N<<1],siz[N],vis[N],mn,E,gs;
    ll dis[N],dep[N];vector<int>p[N];
    bool cmp(int x,int y) {return T2::dfn[x]<T2::dfn[y];}
    struct node {
        int x,v;
        node(int _x=0,int _v=0) {x=_x,v=_v;}
        bool operator!=(node a) const {return x!=a.x||v!=a.v;}
    };
    vector<node>g[N];
    void Addedge(int x,int y,int z) {g[x].push_back(node(y,z)),g[y].push_back(node(x,z));}
    void Add(int x,int y,int z) {nx[++cnt]=h[x],to[h[x]=cnt]=y,vl[cnt]=z,nx[++cnt]=h[y],to[h[y]=cnt]=x,vl[cnt]=z;}
    void Rebuild(int x,int fa) {
        int las=x;
        for(auto y:g[x])if(y.x!=fa&&(Add(las,y.x,y.v),y!=g[x].back()))Add(las,++gs,0),las=gs;
        for(auto y:g[x])if(y.x!=fa)Rebuild(y.x,x);
    }
    void Dfs(int x,int fa) {for(int i=h[x]; i; i=nx[i])if(to[i]!=fa)dep[to[i]]=dep[x]+vl[i],Dfs(to[i],x);}
    void Getsz(int x,int fa) {siz[x]=1;for(int i=h[x],y; i; i=nx[i])if(!vis[i>>1]&&(y=to[i])!=fa)Getsz(y,x),siz[x]+=siz[y];}
    void Gete(int x,int fa,int Sz) {
        for(int i=h[x],y,tmp; i; i=nx[i]) {
            if(vis[i>>1]||(y=to[i])==fa)continue;
            Gete(y,x,Sz);if((tmp=max(siz[y],Sz-siz[y]))<mn)mn=tmp,E=i>>1;
        }
    }
    int Getg(int x) {return mn=2e9,E=0,Getsz(x,0),Gete(x,0,siz[x]),E;}
    void Merge(int x,int y,int z) {
        int i=0,j=0,sx=p[x].size(),sy=p[y].size();
        while(i<sx||j<sy)if(j>=sy||(i<sx&&T2::dfn[p[x][i]]<T2::dfn[p[y][j]]))p[z].push_back(p[x][i++]);else p[z].push_back(p[y][j++]);
    }
    void Get(int x,int fa,int opt) {
        W[x]=dep[x]+dis[x],is[x]=opt;
        for(int i=h[x],y; i; i=nx[i]) {if(vis[i>>1]||(y=to[i])==fa)continue;dis[y]=dis[x]+vl[i],Get(y,x,opt);}
    }
    void Divide(int g) {
        vis[g]=1;int e1,e2,x=to[g<<1],y=to[g<<1|1];
        if(e1=Getg(x))Divide(e1);if(e2=Getg(y))Divide(e2);
        Get(x,dis[x]=0,0),dis[y]=vl[g<<1],Get(y,0,1);
        if(!e1&&!e2) {if(x<=n)p[g].push_back(x);if(y<=n)p[g].push_back(y);sort(p[g].begin(),p[g].end(),cmp);}
        else {if(p[0].clear(),!e1){if(x<=n)p[0].push_back(x);}else {if(y<=n)p[0].push_back(y);}Merge(e1,e2,g);}T2::Solve(p[g]),vis[g]=0;
    }
}
int main() {
    T1::gs=n=read();
    Log[0]=-1;for(int i=1; i<=n; ++i)Log[i]=Log[i>>1]+1,is[i]=-1,T2::f1[i]=T2::f2[i]=-inf;
    for(int i=1,x,y,z; i<n; ++i)x=read(),y=read(),z=read(),T1::Addedge(x,y,z);
    for(int i=1,x,y,z; i<n; ++i)x=read(),y=read(),z=read(),T2::Addedge(x,y,z);
    T1::Rebuild(1,0),T1::Dfs(1,0),T2::Dfs(1,0),T2::Pre(),T1::Divide(T1::Getg(1));
    for(int i=1; i<=n; ++i)ans=max(ans,T1::dep[i]-T2::dis[i]);
    cout<<ans;
    return 0;
}