浅谈一类点分治优化 DP

· · 算法·理论

可能更好的阅读体验

1. 引入与介绍

对于一类树上连通块或路径问题，合并子树（可以看作卷积）的复杂度很高，但是插入一个点和自己与自己合并（可以看作点积）的复杂度可以用点分治来进行优化。

以一道例题引入：Ridiculous Netizens - HDU 6643

首先你会想到用树形背包来做，但是问题在于如果你直接设置为 f(u,i) 表示为 u 子树内乘积为 i 的方案数，但是直接做会出现两个问题：

先保证状态是 O(nm)，然后我们考虑把第一点解决掉，第一点的问题就是在于我们一般树形背包是自底向上合并的，但是这样可能中途就会断掉。

转化思路，我们考虑每个点作为连通块内部的贡献，我们先考虑强制这个连通块经过根，可以发现在这种情况下，如果一个点在连通块中，那么它的父亲必须也在。

自此，由于选取一个点就必须选它的父亲，所以要去选一个子树就必须选这个子树的根。我们可以把原命题转化为一个单点加入问题。

设 f(u,i) 表示 内加入点的构成的子树，乘积为 i 的方案数。先定根，然后我们从根开始自上往下进行 DFS，对于每个点进行选或者不选的决策，如果不选那就不从父亲计算贡献，新开 DP 方案；如果选那就维护从父亲转移过来的贡献，然后 dfs 儿子，最后合并儿子的答案，我们就得到了这个点子树内的答案，对于每一个点枚举其作为连通块的根，然后每个点都暴力跑 DFS 对子树（根节点不能遍历父节点）求出答案。

如果认为自顶向下的 DP 比较难想，当然我们可以在 DFS 序上进行 DP，这样选择一个结点就是转移到 DFS 上的下一个，而跳过一个结点就相当于跳过整棵子树，快速跳转即可。设 f(i,j) 表示 u 子树内 DFS 序考虑到前 i 个节点，乘积为 j 的方案数，同理对于每一个点暴力求出 DFS 序然后进行规划求出答案。

时间复杂度都是 O(n^2m\sqrt{m}) 的。

然后考虑第二个情况，我们不考虑乘积暴力合并是 O(m\sqrt{m}) 的，我们的目标是要优化到 O(n\sqrt{m}) 的状态。看起来很难做，考虑发掘性质，注意到我们枚举约数中使得 i\leftarrow i+1 的时候，所管辖的区间有很多重叠的部分，同时又注意不到，\lfloor \dfrac{x}{nm} \rfloor=\lfloor \dfrac{\dfrac{x}{n}}{m} \rfloor，可以用整除可以把 m 整除 i 的值定义到状态里面。根据整除分块状态数变成 O(\sqrt{m})，根据结论值相同在以后的转移方法也相同所以正确性得到保证，那么状态就变为 O(n\sqrt{m}) 了，但是这不是文章的重点。

说了这么多的求解，终于到优化了。由于上面的统计连通块包含根节点的情况复杂度会到达 O(n^2\sqrt{m})，瓶颈在于子树大小过大，我们考虑如何减小子树规模，发现我们枚举根的情况可以等价于不包含根就分裂成若干个互不相同的子树，变成子问题，重复以上操作。这种情况我们可以思考点分治，降低分割出来的子树大小，可以将复杂度降低到 O(n\sqrt{m} \log n)。

复个小盘，点分治优化 DP 的关键就是在于减小子树规模，降低 DP 的复杂度。一般来说，点分治优化 DP 要求满足以下的条件：

要对于每个连通块求一个什么东西，我们先考虑强制这个连通块经过根，可以发现在这种情况下，如果一个点在连通块中，那么它的父亲必须也在。所以我们先从根自上向下进行 DP，对于每个点进行选/不选的决策，如果不选那就新开一份 dp 去做；如果选那就操作维护父亲对 dp 的贡献，然后 DFS 儿子；最后把儿子的 DP 值的答案合并上来，我们就得到了这个点子树内的答案。当然最后要强制选重心。

以下直接 DFS 实现版本，若 DFN 可以参考 crashed 的题解。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=2e3+15,MM=1e6+15,INF=1e18,MOD=1e9+7;
int n,m,a[MN],w[MN],st[MM],ctot,ans,f[MN][MN];
vector<int> adj[MN];

namespace Tree{
    int dep[MN],maxp[MN],siz[MN],dfn[MN],rt,sum;
    bool vis[MN];

    void dfs1(int u,int pre){ // getrt
        siz[u]=1;
        maxp[u]=0;
        for(auto v:adj[u]){
            if(v==pre||vis[v]) continue;
            dfs1(v,u);
            siz[u]+=siz[v];
            maxp[u]=max(maxp[u],siz[v]);
        }
        maxp[u]=max(maxp[u],sum-siz[u]);
        if(maxp[u]<maxp[rt]) rt=u;
    }

    void dfs2(int u,int pre){
        for(int i=1;i<=ctot;i++) f[u][i]=0;
        for(int i=1;i<=ctot;i++){
            if(w[i]>=a[u]){
                (f[u][st[w[i]/a[u]]]+=f[pre][i])%=MOD;
            }
        }
        for(auto v:adj[u]){
            if(vis[v]||v==pre) continue;
            dfs2(v,u);
            for(int i=1;i<=ctot;i++){
                (f[u][i]+=f[v][i])%=MOD;
            }
        }
    }

    void calc(int u){
        f[0][ctot]=1;
        dfs2(u,0);
        for(int i=1;i<=ctot;i++){
            (ans+=f[u][i])%=MOD;
        }
        f[u][ctot]=0;
    }

    void solve(int u){
        vis[u]=1;
        calc(u);
        for(auto v:adj[u]){
            if(vis[v]) continue;
            sum=siz[v];
            maxp[rt=0]=INF;
            dfs1(v,0);
            solve(rt);
        }
    }

}using namespace Tree;

void init(){
    rt=ans=0;
    sum=0;
    for(int i=1;i<=n;i++){
        adj[i].clear();
        vis[i]=0;
        a[i]=0;
        dfn[i]=maxp[i]=dep[i]=siz[i]=dfn[i]=0;
    }
    for(int i=1;i<=ctot;i++){
        st[w[i]]=0;
        w[i]=0;
    }
    ctot=0;
}

void prework(){
    for(int i=m,ls=0;i>=1;i--){
        int x=m/i;
        w[st[x]=x!=ls?++ctot:ctot]=x;
        ls=x;
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=ctot;j++){
            f[i][j]=0;
        }
    }
}

void solve(){
    cin>>n>>m;
    init();
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    prework();
    maxp[rt=0]=sum=n;
    dfs1(1,0);
    solve(rt);
    cout<<ans<<'\n';
}

signed main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

2. 例题

HDU 5909

有点眼熟啊，不是吗，只不过换成了异或。

但是我知道，这不位运算吗？我会 FWT！这个背包显然你一开始就说是卷积，我用脚都会，时间复杂度 O(nm\log m)，轻松水过。

但显然我不是要讲这个做法，考虑到这个玩意直接做背包很难，但是单独加入一个点的复杂度近乎 O(1)，并且一个点选了，其儿子才能选，否则其儿子不能选，一眼连通块加树上依赖背包。直接转 DFS 序上 DP。设 f(i,j) 表示 u 子树内 DFS 序考虑到前 i 个节点，异或和为 j 的方案数，暴力显然是 O(n^2m) 的，但是点分治就能够做到 O(nm\log n)。

CodeChef SUBWAY

注意有中文题面，首先这是一颗有重边的树，可以看成每条边选择一个颜色，让相邻边不同的最多。

然后考虑分析性质，发现一个树有很多重边甚是卑鄙，考虑简化问题。我们发现如果一条边有三种颜色，那么这条边一定可以选出一种颜色使得于另外两边颜色都不相同，所以可以看成只有一种以前没有出现过的颜色。所以每条边我们至多保留两个颜色即可。

其次，我们求的是同色路径，如果我们直接自底向上进行合并的话会因为要求联通而不行，我们还是和上面一样的方法，枚举根 rt 也就是起点，让后自上向下进行拓展，用 DP 计算方案，设 f(i,j,k) 表示当前到 i 点，从 rt 进入包含 i 点子树选择的边颜色为第 j 个（共两个，取值 0/1），父亲到 i 点选择边颜色为第 k 种，仍为 0/1 变量。这样状态设计可以很方便地满足我们自上向下进行拓展。转移暴力拓展其子树即可，时间复杂度 O(n^2)，无法通过。但是注意到本问题和根选择无关，只需要确定一种顺序即可，我们可以通过点分治优化这一过程，时间复杂度 O(n\log n)。

同时本题显然存在倍增 DP 做法，状态同上但是加入了倍增必须的 2^j，我写了，我大输特输，直接当场暴毙。

3.参考

求赞 QwQ。