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

· · 题解

撇一篇 DSU on tree + 动态点分 的题解。

首先套路地把原式化成 \frac{1}{2}\max\{dis(i,j)+dep(i)+dep(j)-2dep'(lca'(i,j))\} 。

在第二棵树上枚举 p=lca'(i,j) 。根据 DSU on tree 的套路，我们要先递归解决 p 的所有轻子树内部的答案，然后解决掉 p 的重子树并继承信息。

接下来，考虑枚举 p 的轻子树内的点 q ，并在计算完处于 p 的同一个儿子内的点的答案之后，将这些点与 p 之前的子树合并。

我们现在已知了 dep'(p) 和 dep(q) ，因此我们还需要对于每个重子树节点 r ，维护 \max\{dis(q,r)+dep(r)\} 。

这相当于：在第一棵树上标记关键点（实际相当于新建一个关键点，并由这个点向 r 连接一条长度为 dep(r) 的边。但是显而易见的是这个新加的关键点并不需要显式地加入，直接在点 r 处插入即可），并多次询问一个点到当前关键点集的最大距离。

对第一棵树建立点分树，每个点上维护三个值：这个点代表分治范围下的最远距离的值 fir ；最远距离的点所属的子树 frm 和不与最远点同属一子树的次远距离 sec 。

询问，修改都可以暴力跳点分树进行修改。

坑：由于这样算的是两两不同的点对的答案，最后要单独算 i 和它自己的答案。

复杂度分析：每个点会被插入、查询 O(\log_2n) 次，单次操作复杂度 O(\log_2n) 。因此总复杂度 O(n\log_2^2n) 。

实际上这玩意由于出题人倾向于卡错误复杂度的边分治，因此跑得飞快，甚至和某些单 \log 的做法效率相当（

理论复杂度和程序运行效率没有任何关系。 —— 某oier

Code: 

#include<bits/stdc++.h>
int n;
typedef long long ll;
const ll INF=1e18;
ll ans=-INF;
struct pii{int t,l;};
struct intree
{
    std::vector<pii>v[377777];
    int sz[377777],ds[377777],d[377777],fa[377777][22];
    ll dep[377777];
    void dfs(int p=1,int f=0)
    {
        sz[p]=1,d[p]=d[f]+1,fa[p][0]=f;
        for(register int i=0;fa[p][i];i++)fa[p][i+1]=fa[fa[p][i]][i];
        for(pii t:v[p])if(t.t^f)
            dep[t.t]=dep[p]+t.l,dfs(t.t,p),
            sz[p]+=sz[t.t],sz[ds[p]]<sz[t.t]?ds[p]=t.t:0;
    }
    int lca(int x,int y)
    {
        if(d[x]<d[y])x^=y^=x^=y;
        register int i,ii;
        for(ii=d[x]-d[y],i=0;ii;ii>>=1,i++)
            if(ii&1)x=fa[x][i];
        if(x==y)return x;
        for(i=18;~i;i--)
            if(fa[x][i]^fa[y][i])x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
    ll dis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}
    void rd()
    {
        register int i;
        for(i=1;i<n;i++)
        {
            int x,y,l;
            scanf("%d%d%d",&x,&y,&l),
            v[x].push_back(pii{y,l}),
            v[y].push_back(pii{x,l});
        }dfs();
    }
}T1,T2;
inline void emax(ll&x,ll y){x<y?x=y:0;}
namespace tree
// 动态点分治部分
{
    int tfa[377777],col[377777],tsz[377777];
    void dfs(int p,int f=0)
    {
        tsz[p]=1;
        for(pii t:T1.v[p])
            if(t.t^f)if(!col[t.t])
                dfs(t.t,p),tsz[p]+=tsz[t.t];
    }
    int getg(int p)
    {
        dfs(p);int GS=tsz[p];
        for(;;)
        {
            for(pii t:T1.v[p])
                if(tsz[t.t]<tsz[p]&&((tsz[t.t]<<1)>=GS)&&!col[t.t])
                    {p=t.t;goto RE;}
            return p;
            RE:;
        }
    }
    int split(int p=1,int d=1)
    {
        p=getg(p),col[p]=d;
        for(pii t:T1.v[p])if(!col[t.t])tfa[split(t.t,d+1)]=p;
        return p;
    }
    ll le[377777][22];
    ll dev[377777],fir[377777],sec[377777];
    int frm[377777];
    std::vector<int>inserted_list;
    void ins(int x)
    {
        inserted_list.push_back(x);
        register ll Z=dev[x]=T1.dep[x];
        for(register int i=1,f=x;;i++)
        {
            int y=tfa[x];
            if(!y)return;
            ll dc=le[f][i]+Z;
            if(dc>fir[y])
            {
                if(x!=frm[y])
                    sec[y]=fir[y],fir[y]=dc,frm[y]=x;
                else fir[y]=dc;
            }else if(dc>sec[y])if(x!=frm[y])sec[y]=dc;
            x=y;
        }
    }
    void rem(int x)
    {
        for(dev[x]=-INF;x;x=tfa[x])fir[x]=sec[x]=-INF,frm[x]=0;
    }
    void clear()
    {
        for(int t:inserted_list)rem(t);
        inserted_list.clear();
    }
    ll ask(int x)
    {
        ll ret=dev[x];
        for(register int i=1,f=x;;i++)
        {
            int y=tfa[x];
            if(!y)return ret;
            emax(ret,dev[y]+le[f][i]);
            if(x!=frm[y])emax(ret,fir[y]+le[f][i]);
            else emax(ret,sec[y]+le[f][i]);
            x=y;
        }
    }
    void init()
    {
        split(1);
        for(register int i=1,ii,x;i<=n;i++)
        {
            emax(ans,2*(T1.dep[i]-T2.dep[i])),rem(i);
            for(x=tfa[i],ii=1;x;x=tfa[x],ii++)
                le[i][ii]=T1.dis(i,x);
        }
    }
}
std::vector<int>tmp;
void dsurec(int p,int f)
{
    tmp.push_back(p);
    for(pii t:T2.v[p])if(t.t^f)dsurec(t.t,p);
}
void dsu(int p=1,int f=0,bool light=1)
// 算法核心：light 表示这个点到父亲的边是否是轻边。
// 当 light=1 时，舍弃 p 的子树信息。否则保留 p 的子树信息。
{
    for(pii t:T2.v[p])if(t.t^f)if(t.t^T2.ds[p])dsu(t.t,p);
    if(T2.ds[p])
    {
        dsu(T2.ds[p],p,0),emax(ans,-T2.dep[p]*2+T1.dep[p]+tree::ask(p)),tree::ins(p);
        for(pii t:T2.v[p])if(t.t^f)if(t.t^T2.ds[p])
        {
            tmp.clear(),dsurec(t.t,p);
            for(int x:tmp)emax(ans,-T2.dep[p]*2+T1.dep[x]+tree::ask(x));
            for(int x:tmp)tree::ins(x);
        }
    }else if(!light)tree::ins(p);
    if(light)tree::clear();
}
int main()
{scanf("%d",&n),T1.rd(),T2.rd(),tree::init(),dsu(),printf("%lld\n",ans>>1);}