题解 P4565 【[CTSC2018]暴力写挂】

disangan233 · 2019-04-24 20:12:17 · 题解

大家好这里是点名被卡的 O\left(n\log^2{n}\right) 做法。

PS：感谢 yyb大佬的博客给蒟蒻的参考。

题意

给你两颗树 tree1、tree2，让你求出：

\mathrm{max} \left\{ dep(x)+dep(y)-dep(lca(x,y))-dep'(lca'(x,y)) \right\}

其中：

x,y,lca(x,y)\in \{ tree1\}\ \ \ x,y,lca'(x,y) \in \{tree2\}

显然 dep'(lca'(x,y)) 不能直接求，考虑树形 dp。

于是我们只需要巧妙地求出 dep(x)+dep(y)-dep(lca(x,y)) 即可。

考虑改一下式子：

Ans=\dfrac{1}{2}\left( dep(x)+dep(y)+dis(x,y)\right)

因为出现了 dis(x,y)，考虑对于 tree1 进行边分治，然后对于tree2 进行 dp。

这样的时间复杂度是 O\left( n^2\log{n}\right)，树形 dp 复杂度为 O(n)。

考虑优化，跑虚树 dp，这样就可以做到 O\left(n\log^2{n}\right)啦！会 TLE 一个点。

tricks

倍增 lca 太慢了，考虑 O(n\log{n})-O(1) 的 RMQ-LCA，可以拿来卡卡常数。

可以通过基数排序做到 O\left(n\log{n}\right)，但是窝太菜了，加加编译优化松松松就过了。

Code(复制会Re)

// 保证不影响观看
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ak *
#define ll long long
inline char getch()
{
    static char buf[10000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++;
}
#define gc() getch()
char qwq;
inline ll read()
{
    ll cz=0,ioi=1;qwq=gc();
    while(qwq<'0'||qwq>'9') ioi=qwq=='-'?~ioi+1:1,qwq=gc();
    while(qwq>='0'&&qwq<='9') cz=(cz<<3)+(cz<<1)+(qwq^48),qwq=gc();
    return cz ak ioi;
}
const int M=400005;
int ans[2][M],num[2],tp[M],m;
ll res=-1e18,w[M];
namespace t2
{
    int cnt=1,h[M],dfn[M],low[M],sum,tim,dep[M],st[M<<1][21];
    int lg2[M<<1],fir[M],vis[M];
    ll f[M][2],dis[M];
    struct did{int next,to;ll w;}e[M<<1];
    void add(re x,re y,ll z) {e[++cnt]=(did){h[x],y,z},h[x]=cnt;}
    void dfs(re u,re fa)
    {
        dep[u]=dep[fa]+1;dfn[u]=++tim;
        st[++sum][0]=u;fir[u]=sum;
        for(re i=h[u],v;v=e[i].to,i;i=e[i].next)
        {
            if(v==fa) continue;
            dis[v]=dis[u]+e[i].w;dfs(v,u);
            st[++sum][0]=u;
        }
        low[u]=tim;
    }
    int cmp(re x,re y) {return dep[x]<dep[y]?x:y;}
    void ST()
    {
        for(re i=2;i<=sum;i++) lg2[i]=lg2[i>>1]+1;
        for(re j=1;j<=lg2[sum];j++)
        for(re i=1;i+(1<<j)-1<=sum;i++)
        st[i][j]=cmp(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        memset(h,0,sizeof(h));
    }
    int lca(re u,re v)
    {
        u=fir[u],v=fir[v];if(u>v) swap(u,v);
        re k=lg2[v-u+1];
        return cmp(st[u][k],st[v-(1<<k)+1][k]);
    }
    void dp(re u,ll sum)
    {
        f[u][0]=f[u][1]=-1e18;
        if(vis[u]) f[u][tp[u]]=w[u];
        for(re i=h[u],v;v=e[i].to,i;i=e[i].next)
        {
            dp(v,sum);ll nw=max(f[u][0]+f[v][1],f[u][1]+f[v][0]);
            res=max(res,sum+nw-2*dis[u]);
            f[u][0]=max(f[u][0],f[v][0]);
            f[u][1]=max(f[u][1],f[v][1]);
        }
        vis[u]=h[u]=0;
    }
    int q[M<<1],stk[M],tot;
    bool dfn_cmp(int a,int b){return dfn[a]<dfn[b];}
    void svt(ll sum)
    {
        cnt=1;tot=0;
        for(re i=1;i<=num[0];i++) q[++tot]=ans[0][i];
        for(re i=1;i<=num[1];i++) q[++tot]=ans[1][i];
        for(re i=1;i<=tot;i++) vis[q[i]]=1;
        sort(q+1,q+tot+1,dfn_cmp);
        re top=0; if(q[1]!=1) stk[++top]=1;
        for(re i=1;i<=tot;i++)
        {
            re u=q[i],v=lca(u,stk[top]);
            while(top>1&&dep[stk[top-1]]>=dep[v])
            add(stk[top-1],stk[top],0),top--;
            if(v!=stk[top]) add(v,stk[top],0),stk[top]=v;
            stk[++top]=u;
        }
        while(top>1) add(stk[top-1],stk[top],0),top--;
        dp(1,sum);
    }
};
namespace t1
{
    int cnt=1,h[M<<2],size[M<<2],vis[M<<2],n,ct,maxn;
    ll dis[M<<2],dep[M<<2];
    struct did{int next,to;ll w;}e[M<<3];
    struct par{int a,b;par() {} par(re x,re y) : a(x),b(y) {}};
    vector<par>ve[M<<2];
    void add(re x,re y,ll z)
    {
        e[++cnt]=(did){h[x],y,z},h[x]=cnt;
        e[++cnt]=(did){h[y],x,z},h[y]=cnt;
    }
    void pre(re u,re fa)
    {
        for(re i=h[u],v;v=e[i].to,i;i=e[i].next)
        {
            if(v==fa) continue;
            ve[u].push_back(par(v,e[i].w));
            dep[v]=dep[u]+e[i].w,pre(v,u);
        }
    }
    void rebuild()
    {
        memset(h,0,sizeof(h));cnt=1;
        for(re x=1;x<=n;x++)
        {
            re sz=ve[x].size();
            if(sz<=2)
            {
                for(re i=0;i<sz;i++)
                add(x,ve[x][i].a,ve[x][i].b);
            }
            else
            {
                re ls=++n,rs=++n;
                add(x,ls,0);add(x,rs,0);
                for(re i=0;i<sz;i++)
                ve[i&1?ls:rs].push_back(par(ve[x][i].a,ve[x][i].b));
            }
        }
    }
    void find_ct(re u,re fa,re sum)
    {
        size[u]=1;
        for(re i=h[u],v;v=e[i].to,i;i=e[i].next)
        {
            if(v==fa||vis[i>>1]) continue;
            find_ct(v,u,sum);size[u]+=size[v];
            re now=max(size[v],sum-size[v]);
            if(maxn>now) maxn=now,ct=i;
        }
    }
    void dfs(re u,re fa,re pos)
    {
        if(u<=m) ans[pos][++num[pos]]=u,tp[u]=pos;
        for(re i=h[u],v;v=e[i].to,i;i=e[i].next)
        {
            if(v==fa||vis[i>>1]) continue;
            dis[v]=dis[u]+e[i].w,dfs(v,u,pos);
        }
    }
    bool getans()
    {
        if(!num[0]&&!num[1]) return 0;
        for(re i=1;i<=num[0];i++) w[ans[0][i]]+=dis[ans[0][i]]+dep[ans[0][i]];
        for(re i=1;i<=num[1];i++) w[ans[1][i]]+=dis[ans[1][i]]+dep[ans[1][i]];
        t2::svt(e[ct].w);
        for(re i=1;i<=num[0];i++) w[ans[0][i]]-=dis[ans[0][i]]+dep[ans[0][i]];
        for(re i=1;i<=num[1];i++) w[ans[1][i]]-=dis[ans[1][i]]+dep[ans[1][i]];
        return 1;
    }
    void divide(re u,re sum)
    {
        maxn=1e9,find_ct(u,0,sum);
        if(maxn>=1e9) return;
        re s=e[ct].to,t=e[ct^1].to;vis[ct>>1]=1;
        num[0]=num[1]=dis[s]=dis[t]=0;
        dfs(s,0,0);dfs(t,0,1);
        if(!getans()) return;
        re nw=ct,ss=sum-size[e[nw].to];
        divide(s,size[e[nw].to]);divide(t,ss);
    }
};
int main()
{
    int sized=40<<20;
    __asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(sized)+sized));
    t1::n=m=read();
    for(re i=1;i<m;i++)
    {
        re x=read(),y=read(),z=read();
        t1::add(x,y,z);
    }
    for(re i=1;i<m;i++)
    {
        re x=read(),y=read(),z=read();
        t2::add(x,y,z);t2::add(y,x,z);
    }
    t1::pre(1,0);t1::rebuild();
    t2::dfs(1,0);t2::ST();
    t1::divide(1,t1::n);
    res/=2;
    for(re i=1;i<=m;i++) res=max(res,t1::dep[i]-t2::dis[i]);
    printf("%lld\n",res);
    return 0; 
}