题目传送门

这是一个树剖+序列分块。感觉因为单纯树剖跑不满 log，比树上k级祖先+根号分治的做法要快一些。

对于查询的两个端点，记余数 $m_u,m_v$ 为 $1$。

每次树剖跳 $u$ 的时候，在序列上查询这一段模数为 $k$，且下标（从1开始）余数为 $m_u$ 的和，再令 $m_u=(m_u-l)\mod k$（$l$ 是查询区间的长度）。跳 $v$ 同理。

对 dfs 序进行分块，块大小为 $S$。每块对于 $1\leq k\leq S$ 的模数预处理出下标（从1开始）余数为 $0\leq m<k$ 的和。

散块暴力跳，跑完每个块，余数类似树剖那段进行变化。

如果查询的 $k\geq S$，就直接暴力跳整个区间。

一个小问题是树剖是倒着跳的，在正的 dfs 序上查询余数有点麻烦。

所以我们把每个点在 dfs 序上的位置变为 n-dfn[x]+1，相当于分块维护反 dfs 序。

本质类似根号分治做法，但充分利用了树剖的特性而不是每次就只跳 $S$。

取 $S=\sqrt{n}$，时间 $O(n\lg n\sqrt{n})$，空间 $\Theta(n\sqrt{n})$。

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    char c;int x,f{0};
    do x=(c=getchar())^48;
    while (!isdigit(c)&&c!='-');
    if (x==29) f=-1,x=0;
    while (isdigit(c=getchar()))
        x=(x<<3)+(x<<1)+(c^48);
    return (x^f)-f;
}
const int N(5e4),B{223*20},K{N/B+1};
// val是dfs序上的点权
int sum[B+5][K][K],val[N+5],a[N+5],n;
inline int R(int b){return b*K;}
inline int L(int b){return R(b-1)+1;}
inline int bl(int x){return (x-1)/K+1;};
int ppip(int l,int r,int k,int m)
{
    if (!m) m=k;
    int ans{0};
    for (int i{l+m-1};i<=r;i+=k)
        ans+=val[i];
    return ans;
}
// 序列分块
int query(int l,int r,int k,int m){
    if (bl(l)==bl(r)) return ppip(l,r,k,m);
    int ans{ppip(l,R(bl(l)),k,m)};
    m=(m+k-(R(bl(l))-l+1)%k)%k;
    assert(R(bl(r)-1)<=n);
    for (int i{bl(l)+1};i<bl(r);++i) {
        if (k>=K) {
            if (k==K&&m==0) ans+=val[R(i)];
            else if (m<=K&&m) ans+=val[L(i)+m-1];
        } else ans+=sum[i][k][m];
        m=(m+k-K%k)%k;
    }
    ans+=ppip(L(bl(r)),r,k,m);
    return ans;
}
int fa[N+5],dep[N+5],sz[N+5],son[N+5],tp[N+5];
int dfn[N+5];
vector<int> e[N+5];
// 树剖
void fz_init(int u,int f){
    fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
    for (auto v:e[u])
        if (v!=f) {
            fz_init(v,u);
            sz[u]+=sz[v];
            if (sz[v]>sz[son[u]])
                son[u]=v;
        }
}
void fz_cut(int u,int top){
    static int cxx{1};
    tp[u]=top;dfn[u]=cxx++;
    if (son[u]) fz_cut(son[u],top);
    for (auto v:e[u])
        if (v!=fa[u]&&v!=son[u])
            fz_cut(v,v);
}
int query(int u,int v,int k){
    int wu{1%k},wv{1%k},ans{0};
    while (tp[u]!=tp[v]){
        if (dep[tp[u]]<dep[tp[v]])
            swap(u,v),swap(wu,wv);
        // 注意反dfs序反着询问
        ans+=query(dfn[u],dfn[tp[u]],k,wu);
        wu=(wu+k-(dfn[tp[u]]-dfn[u]+1)%k)%k;
        u=fa[tp[u]];
    }
    if (dep[u]<dep[v]) swap(u,v),swap(wu,wv);
    ans+=query(dfn[u],dfn[v],k,wu);
    return ans;
}
int main(){
    n=read();
    for (int i{1};i<=n;++i)
        scanf("%d",a+i);
    for (int i{1};i<n;++i) {
        int a{read()},b{read()};
        e[a].push_back(b);
        e[b].push_back(a);
    }
    fz_init(1,0);fz_cut(1,1);
    for (int i{1};i<=n;++i)
        dfn[i]=n-dfn[i]+1;
    for (int i{1};i<=n;++i)
        val[dfn[i]]=a[i];
    for (int k{1};k<K;++k)
        for (int i{2};i<bl(n);++i)
            for (int j{L(i)};j<=R(i);++j)
                sum[i][k][(j-L(i)+1)%k]+=val[j];
    for (int i{1};i<=n;++i)
        a[i]=read();
    for (int i{1};i<n;++i) {
        int w{read()};
        printf("%d\n",query(a[i],a[i+1],w));
    }
    return 0;
}

随便跑跑就最优解第一页了。

P3591 [POI2015]ODW

POI 合集。

比较套路的根号分治题目。由于当步长 $>B$ 时最多走 $\dfrac n B$ 步，所以我们设置一个阈值 $B$，表示若步长 $\leq B$ 则使用预处理的信息，若步长 $>B$ 则暴力树上倍增计算。

预处理的信息只需要 $v_{k,u}$ 表示 $u$ 每次向上跳 $k$ 步能到达的所有节点权值之和，即 $\sum_{v\in \mathrm{ancestor}(u)}a_v[k\mid dep_u-dep_v]$。可以在 $\mathcal{O}(nB)$ 的复杂度内求得。

综上，时间复杂度 $\mathcal{O}\left(nB+\dfrac{n^2}{B}\log n\right)$，当 $B$ 取 $\sqrt{n\log n}$ 时有理论最优复杂度 $n\sqrt{n\log n}$。如果用长链剖分求树上 $k$ 级祖先则可做到严格 $n\sqrt n$。

由于数据原因，实际表现中取 $B=20$ 会很快。

int n, a[N], b[N], lg[N];
int fa[16][N], dep[N], val[B][N];
vint e[N];
int kthanc(int u, int k) {
	for(int i = lg[k]; ~i; i--) if(k >> i & 1) u = fa[i][u];
	return u;
}
int LCA(int u, int v) {
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = lg[dep[u]]; ~i; i--)
		if(dep[u] - dep[v] >> i & 1) u = fa[i][u];
	if(u == v) return u;
	for(int i = lg[dep[u]]; ~i; i--)
		if(fa[i][u] != fa[i][v]) u = fa[i][u], v = fa[i][v];
	return fa[0][u];
}
void dfs(int id, int f) {
	fa[0][id] = f, dep[id] = dep[f] + 1;
	for(int i = 1; i <= lg[dep[id]]; i++) fa[i][id] = fa[i - 1][fa[i - 1][id]];
	for(int i = 1, v = f; i < B; i++, v = fa[0][v])
		val[i][id] = a[id] + val[i][v];
	for(int it : e[id]) if(it != f) dfs(it, id);
}

int main() {
	cin >> n;
	for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
	for(int i = 1; i <= n; i++) a[i] = read();
	for(int i = 1, u, v; i < n; i++) e[u = read()].pb(v = read()), e[v].pb(u);
	dfs(1, 0);
	for(int i = 1; i <= n; i++) b[i] = read();
	for(int i = 1, u, v, c; i < n; i++) {
		c = read(), u = b[i], v = b[i + 1];
		int d = LCA(u, v), ans = 0;
		if(c >= B) {
			ans = a[u] + a[v];
			while(1) {
				int anc = kthanc(u, c);
				if(dep[anc] < dep[d]) break;
				if(v == d && anc == d) break;
				ans += a[anc], u = anc;
			}
			int gap = dep[u] + dep[v] - (dep[d] << 1);
			if(gap % c) {
				int anc = kthanc(v, gap % c);
				if(dep[anc] > dep[d]) ans += a[anc], v = anc;
			}
			while(1) {
				int anc = kthanc(v, c);
				if(dep[anc] <= dep[d]) break;
				ans += a[anc], v = anc;
			}
		} else if(d == v)
			ans = a[v] + val[c][u] -
				val[c][kthanc(u, (dep[u] - dep[v] - 1) / c * c + c)];
		else {
			int gap = dep[u] - dep[d];
			int anc = kthanc(u, gap / c * c + c);
			ans += val[c][u] - val[c][anc];
			gap = dep[u] + dep[v] - (dep[d] << 1);
			if(gap % c) {
				int anc = kthanc(v, gap % c);
				if(dep[anc] > dep[d]) ans += a[v], v = anc;
			}
			if(v != d) {
				anc = kthanc(v, (dep[v] - dep[d] - 1) / c * c + c);
				ans += val[c][v] - val[c][anc];
			}
		} print(ans), pc('\n');
	}
	return flush(), 0;
}