题解：P5399 [Ynoi2018] 駄作

· · 题解

拼尽全力无法战胜最优解，不过应该取得了最大点最快的最优解（2.11s），写篇题解记录一下卡常技巧。

思路

树分块

目的：将树分成 \mathcal O(\dfrac{n}{B}) 个连通块，每个块的大小均为 \mathcal O(B)，任意两个连通块的交集至多为 1，连通块并集为所有点。每个连通块与其他连通块共同包含的点至多有两个，在上面的称作上界点，在下面的称作下界点，它们一定满足祖先关系。

做法：

后序遍历整个树，到一个点的时候遍历它的儿子，将当前儿子前的一段连通块加入当且仅当：

如果分过至少一个连通块，则将当前点标记为下界点。

具体实现的时候需要先倒序遍历所有儿子并使用一个栈记录还没分连通块的点（因为需要知道下一个点的节点情况所以需要先遍历，因为使用栈所以倒序遍历）。需要一个变量记录当前连通块的下界点，一个布尔变量记录是否分过至少一个连通块。

代码：

int nxt[100010];
int siz[100010];
int down[100010];
int tot=0,st[100010];
int ttot=0,rt[100010],id[100010];
int fa2[100010],dep2[100010];
void build(int u)
{
    int lst=0;
    for(int i=e1[u].size()-1; i>=0; --i)
    {
        int v=e1[u][i];
        build(v);
        nxt[v]=lst,lst=v;
    }
    int nowrt=0; bool vis=0;
    for(int v:e1[u])
    {
        siz[u]+=siz[v];
        if(down[v]!=0) nowrt=down[v];
        if(siz[u]>=B || (nowrt!=0 && down[nxt[v]]!=0) || (nxt[v]==0 && ((vis && nowrt!=0) || fa1[u]==0)))
        {
            rt[++ttot]=nowrt,fa2[ttot]=u;
            while(siz[u]!=0) id[st[tot]]=ttot,--tot,--siz[u];
            nowrt=0,vis=1; 
        }
    }
    down[u]=(vis?u:nowrt);
    ++siz[u],st[++tot]=u;
}

rt[0]=1,fa2[0]=ttot+1;
for(int i=ttot; i>=1; --i) fa2[i]=id[fa2[i]],dep2[i]=dep2[fa2[i]]+1;

连通块数量和大小量级证明：

上述思路是我看题解没看明白后自己发明的，可能不是最优的。

这道题

考虑对块内和两个块之间的答案分别统计。

块内：对于询问的点所在的块，可以计算每条边的贡献：子树内满足 d(p_0,u) \le d_0 的个数乘上子树外满足 d(p_1,u) \le d_1 的个数，以及将 p_0,d_0 和 p_1,d_1 对调之后的答案。可以暴力计算。对于其他的块，p_0 一定是从两个界点中的一个进入这个块的（可以使用两个界点到 p_0 的距离判断），之后转化为了两个界点中的一个在块内的邻域。可以预处理 ycl_{i,0/1,j,0/1,k} 表示在第 i 个块内对于 p_0/p_1 的邻域，距离某个界点分别为 j,k 的答案。可以在块内预处理并使用二维前缀和求出。

块外：将块外的答案分成两部分：这个块内的所有点汇合到某个界点的距离乘上界点上面或者下面满足条件的点的个数，以及两个块之间的边（体现为一个其他块的上界点与下界点的距离）乘上它上下的满足条件的点的个数。因此我们只需要对每个块预处理出 p_0/p_1 满足条件的点到两个节点的距离以及满足条件的点的个数即可。对于 p_0/p_1 所在的块，可以暴力求。否则预处理 yycl_{i,0/1,0/1,j} 表示第 i 个块内距离某个界点 \le j 的所有点到某个界点的距离之和即可。

具体实现的时候可以先逐块处理求出块内的所有贡献以及 p_0/p_1 所在块的信息，之后再将所有块放到一起求块外的贡献。

卡常技巧

这里介绍一个优化效果非常好的卡常技巧。

考虑将树重新编号，使得每一个树分块的连通块内部编号连续，且整体仍然满足 dfs 序。这是容易达到的。在递归过程中，先遍历与它属于同一个块的所有儿子，再遍历与它不属于同一个块的所有儿子。两次遍历的过程中都需要将同一个块的一段先提出来，最后遍历有界点的儿子。

这样的话几乎所有地方就都访问连续了。而且还有一个更加美好的优化：考虑使用 dfs 序求 lca（详见 Alex_wei 的博客），那么对于 u<v，lca(u,v)=\min_{i=u+1}^v fa_i。对于编号连续的一段区间的 dis 预处理时，lca 就只需要一个变量记录，并不断取 \min 了。这样会有非常大的优化。

在块外的贡献需要求出 p_0/p_1 到某个界点的距离，之前记录的是 f_{i,j} 表示第 i 个界点到 j 的距离，但是现在访问方式变了，如果再使用 f 会非常慢。一个非常神奇的优化是，直接预处理 g_{j,i}=f_{i,j}，再调用 g 就访问连续了。预处理 g 的时候要按照 g 的顺序而不是 f 的顺序（后者会非常慢），这样的话非常快。

代码：

int cnt=0,idd[100010];
void dfs(int u)
{
    idd[u]=++cnt;
    for(int i=0; i<e1[u].size(); ++i)
    {
        if(id[e1[u][i]]!=id[u]) continue;
        int now=i,wz=-1;
        while(now<e1[u].size() && id[e1[u][now]]==id[e1[u][i]])
        {
            if(down[e1[u][now]]!=0) wz=now;
            ++now;
        }
        --now;
        for(int j=i; j<=now; ++j) if(j!=wz) dfs(e1[u][j]);
        if(wz!=-1) dfs(e1[u][wz]);
        i=now;
    }
    for(int i=0; i<e1[u].size(); ++i)
    {
        if(id[e1[u][i]]==id[u]) continue;
        int now=i,wz=-1;
        while(now<e1[u].size() && id[e1[u][now]]==id[e1[u][i]])
        {
            if(down[e1[u][now]]!=0) wz=now;
            ++now;
        }
        --now;
        for(int j=i; j<=now; ++j) if(j!=wz) dfs(e1[u][j]);
        if(wz!=-1) dfs(e1[u][wz]);
        i=now;
    }
}

for(int i=0; i<=ttot; ++i)
{
    if(rt[i]==0) memset(diis[i],0x3f,sizeof(diis[i]));
    else
    {
        diis[i][rt[i]]=0;
        int lca=1e9;
        for(int j=rt[i]+1; j<=n; ++j) lca=min(lca,fa1[j]),diis[i][j]=dis[rt[i]]+dis[j]-2*dis[lca];
        lca=1e9;
        for(int j=rt[i]-1; j>=1; --j) lca=min(lca,fa1[j+1]),diis[i][j]=dis[rt[i]]+dis[j]-2*dis[lca];
    }
}
memset(diis[ttot+1],0x3f,sizeof(diis[ttot+1]));
for(int i=1; i<=n; ++i)
{
    for(int j=0; j<=ttot+1; ++j) diss[i][j]=diis[j][i];
}

提交记录