【动态规划】长链剖分优化树形 dp

我们在树形 dp 中经常会遇到这样一个模型：

设 \(f_{x,i}\) 表示节点 \(x\) 的子树中深度为 \(x\) 的答案...有递推式： \(f_{x,i} = \sum_{son} f_{son,i - 1/i + 1} \dots\) 。

这样直接做是 \(\Theta(n^2)\) 的，我们考虑去优化这个 dp。

有一个小优化，就是我们想让 \(f_x\) 直接继承一个儿子 \(f_{son}\) 的答案，这时不需要暴力合并，直接过继信息即可。这一点我们可以用分配空间做到，以 \(f_{x,i} = \sum_{son} f_{son,i - 1}\) 为例，就是将 \(f_{son}\) 的头指针设在 \(f_x\) 的头指针后一位，就可以直接得到答案。

考虑直接继承哪一个儿子呢？\(f_{x,i}\) 的 \(i\) 的个数取决于子树 \(x\) 的最大深度，所以我们将子树深度最大的儿子过继即可，容易发现这个就是长链剖分的重儿子。

对于其他儿子，我们直接循环 \(i \in[0,maxdep_{son}]\) 来暴力合并答案。

看似没有优化多少，这时你会发现程序很快，事实上，时间已经优化到了 \(\Theta(n)\) ，下面做分析：

考虑一个点什么时候会被暴力合并，即它是其父亲的轻儿子时，所以它就是一条长链的链顶。然而它被暴力合并需要的次数就是这条长链的长度，而这条长链下面的点都直接过继给父亲，没有暴力合并，相当于每个点在暴力合并中贡献了一次，所以只会合并 \(\Theta(n)\) 次。

模板题 CF1009F Dominant Indices

给定一棵 \(1\) 为根，有 \(n\) 个节点的树，对于每一个节点 \(u\) ，\(d(u,x)\) 为 \(u\) 子树中距离 \(u\) 为 \(x\) 的节点个数，对于每个 \(u\) ，求最小的 \(k\) 且 \(d(u,k)\) 最大。

\(1 \leq n \leq 10^6\) 。

考虑设状态，我们设 \(f_{x,i}\) 为 \(x\) 子树中距离 \(x\) 为 \(i\) 的有多少个，有转移：

与上面说的相符，直接长剖转移即可，对于每个节点记录最大转移点，过继重儿子的时候将转移点判断一下，再继承过来。

对于空间分配，分析上述证明过程可以发现总空间占用也是 \(\Theta(n)\) 的，实现细节见代码。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
vector <int> G[N];
struct Tree{
	int dfn,dep,mxd,siz,fa,top,son;
}t[N];
int val[N * 2],*dp[N],*tp = val,tot = 0,mxp[N],n;
inline void dfs1(int x,int last)
{
	t[x].fa = last;
	t[x].dep = t[last].dep + 1;
	t[x].siz = 1;
	t[x].mxd = 0;
	for(auto to : G[x])
	{
		if(to == last) continue;
		dfs1(to,x);
		t[x].siz += t[to].siz;
		if(t[to].mxd + 1 > t[x].mxd)
		{
			t[x].mxd = t[to].mxd + 1;
			t[x].son = to;
		}
	}
}
inline void dfs2(int x,int last)
{
	t[x].dfn = ++tot;
	if(t[x].son) {dp[t[x].son] = dp[x] + 1; t[t[x].son].top = t[x].top; dfs2(t[x].son,x);}
	for(auto to : G[x])
	{
		if(to == last || to == t[x].son) continue;
		t[to].top = to;
		dp[to] = tp; tp += t[to].mxd + 1;
		dfs2(to,x);
	}
}
inline void dfs3(int x,int last)
{
	dp[x][0] = 1; mxp[x] = 0;
	if(t[x].son) 
	{
		dfs3(t[x].son,x);
		if(dp[x][mxp[t[x].son] + 1] > dp[x][mxp[x]]) mxp[x] = mxp[t[x].son] + 1;
	}
	for(auto to : G[x])
	{
		if(to == last || to == t[x].son) continue;
		dfs3(to,x);
		for(int i = 0;i <= t[to].mxd;i++) 
		{
			dp[x][i + 1] += dp[to][i];
			if(dp[x][i + 1] > dp[x][mxp[x]]) mxp[x] = i + 1;
			else if(dp[x][i + 1] == dp[x][mxp[x]] && mxp[x] > i + 1) mxp[x] = i + 1;
		}
	}
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i = 1,x,y;i <= n - 1;i++)
	{
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs1(1,0);
	t[1].top = 1; dp[1] = tp; tp += t[1].mxd;
	dfs2(1,0);
	dfs3(1,0);
	for(int i = 1;i <= n;i++) cout<<mxp[i]<< '\n';
	return 0;
}

[POI2014] HOT-Hotels

给一棵有 \(n\) 个节点的树，求有多少组点 \((i,j,k)\) 满足两两之间的距离相等。

\(1 \leq n \leq 10^5\) 。

容易发现这样是三元组一定形如一个中心点到三个点的距离相等。这个中心点可以是三个点的 \(lca\) ，也可以在某一个点的子树内。

我们考虑统计下面的一对点，设 \(g_{x,i}\) 表示 \(x\) 的子树内的点对，并且在 \(x\) 上接上一条长为 \(i\) 的链就可以形成贡献的点对数。

也可以定义为： 点对 \((a,b)\) 满足 \(a,b\) 到 \(lca\) 距离为 \(d\) ，都在子树内，且 \(lca\) 和 \(x\) 距离为 \(d - i\) 的 点对数。

我们发现每次 \(g_{x,i}\) 只需要加上在 \(x\) 点汇聚的点对数即可，记 \(f_{x,i}\) 为 \(x\) 子树中距离 \(x\) 为 \(i\) 的点个数，用 \(f\) 可以更新 \(g\) 。

对于每一个儿子 \(son\) ，转移为：

我们考虑同样地长剖优化，将 \(f_{son}\) 的头指针设在 \(f_x\) 后一位，\(g_{son}\) 的头指针设在 \(g_x\) 前一位，所以每次留空间要留两倍。

考虑第一个转移必须要枚举一边，通过重复空间不能转移。

但是我们发现， \(f_{x,i}\) 没有值的情况下是不存在第一种转移的，所以我们可以直接过继重儿子信息，无视第一种转移。

那么我们如何统计答案呢？

考虑 “中心点” 头上的链穿过 \(x\) 的答案，分为两种不重复的情况：

1. 一个点在前面的子树中，两个点在子树 \(son\) 中：\(f_{x,i - 1}g_{son,i}\) 。意思就是 \(son\) 中的点对还需要 \(i\) 的长度，算上 \(son \to x\) 的边，前面子树中到 \(x\) 长度为 \(i - 1\) 的链个数就是答案。

2. 两个点在前面的子树中，一个点在 \(son\) 中：\(g_{x,i}f_{son,i - 1}\) 。同理。

我们可以发现，合并第一个儿子时答案只有一种贡献：就是中心点到 \(x\) 的距离正好等于下面的点对到中心点的距离，我声称这就是 \(g_{son,1}\) （代码里写的是只有一个儿子时的 \(g_{x,0}\) ，是等价的）。

所以过继重儿子的时候也不用统计答案，保证了复杂度为 \(\Theta(n)\) 。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n,a[N],b[N],tot = 0;
vector <int> G[N];
typedef long long ll;
ll v1[N * 5],*f[N],*g[N],*tp = v1,ans = 0;
struct Node{
    int dep,dfn,son,siz,mxd,fa,top;
}t[N];
inline void dfs1(int x,int last)
{
    t[x].dep = t[last].dep + 1;
    t[x].fa = last;
    t[x].siz = 1;
    t[x].mxd = 1;
    for(auto to : G[x])
    {
        if(to == last) continue;
        dfs1(to,x);
        t[x].siz += t[to].siz;
        if(t[to].mxd + 1 > t[x].mxd) t[x].mxd = t[to].mxd + 1,t[x].son = to;
    }
}
inline void dfs2(int x,int last)
{
    t[x].dfn = ++tot;
    if(t[x].son) {t[t[x].son].top = t[x].top; f[t[x].son] = f[x] + 1; g[t[x].son] = g[x] - 1; dfs2(t[x].son,x); }
    for(auto to : G[x])
    {
        if(to == last || to == t[x].son) continue;
        f[to] = tp; tp += 2 * (t[to].mxd + 1);
        g[to] = tp; tp += 2 * (t[to].mxd + 1);
        t[to].top = to;
        dfs2(to,x);
    }
}
inline void dfs3(int x,int last)
{
    f[x][0] = 1; g[x][0] = 0;
    if(t[x].son) {dfs3(t[x].son,x);}
    ans += g[x][0];
    for(auto to : G[x])
    {
        if(to == last || to == t[x].son) continue;
        dfs3(to,x);
        for(int i = 1;i <= t[to].mxd;i++) ans += f[x][i - 1] * g[to][i] + g[x][i] * f[to][i - 1];
        for(int i = 0;i <= t[to].mxd;i++) g[x][i + 1] += f[x][i + 1] * f[to][i];
        for(int i = 0;i <= t[to].mxd;i++) f[x][i + 1] += f[to][i];
        for(int i = 1;i <= t[to].mxd;i++) g[x][i - 1] += g[to][i];
    }
}
int main()
{
    cin>>n;
    for(int i = 1,x,y;i <= n - 1;i++)
    {
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs1(1,0);
    t[1].top = 1; 
    f[1] = tp; tp += 2 * (t[1].mxd + 1); 
    g[1] = tp; tp += 2 * (t[1].mxd + 1);
    dfs2(1,0);
    dfs3(1,0); 
    cout<<ans;
    return 0;
}

[WC2010] 重建计划

给定 \(n\) 个点的树，\(L,U\) ，求一条边数在 \([L,U]\) 之间且边权平均值最大的路径，输出最大值。

\(1 \leq n \leq 10^5\) 。

求平均值最大，考虑 0/1 分数规划，二分这个答案，将每条边权减去 \(mid\) ，找一条 \([L,U]\) 之间的非负权路径。

我会点分！\(\Theta(n \log^3 n)\) 直接带走（详见题解区）。

考虑一个点 \(x\) 子树内所有到 \(x\) 的路径，我们发现长度相同时我们只关注权值最大的一条，所以设 \(f_{x,i}\) 表示 \(x\) 子树中到 \(x\) 的长度为 \(i\) 路径最大权值。

转移：

我们发现这个不能直接继承，需要加一个边，这当然可以线段树区间加，但是更简便的方法是将这个 “最大权值” 改为 “点的最大深度”。

转移变为：

这就可以用长剖直接继承。

答案怎么求呢？

其中 \(maxd_x\) 是 \(x\) 到 \(x\) 所在长链链底的距离。对于 \(f_{x,i}\) ，\(i\) 就被限定在 \([0,maxd_x]\) 中。\(dis_x\) 是 \(x\) 的带权深度。

我们发现这实在需要一个区间 \(\max\) ，而且还带修，所以考虑用线段树维护，单点修改和区间查询最值。将这个 \(f\) 数组套在一个线段树上，原来的指针就变成了下标，剩下的没有变化。

注意这个 \(f_{x,j}\) 指的是合并儿子 \(son\) 之前的 \(f_{x,j}\) ，所以先用临时变量将这个儿子的值存起来，取完 \(ans\) 再更新。

同理，转移重儿子时仍然不需要更新 \(ans\) 。

最后 \(ans\) 可能是某个点到 \(x\) 的祖孙链，再取一下 \(\max_{i \in[L,min(U,maxd_x)]}f_{x,i} - dis_x\) 即可。

由于内层要用线段树维护，时间复杂度 \(\Theta(n \log^2 n)\) 。常数巨大。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
const double eps = 1e-5,inf = LONG_LONG_MAX;
struct Edge{
	int v,next;
	double w;
}e[N * 2];
int head[N],n,L,U,tot = 0;
double mid,ans,tmp[N];
struct Segment_Tree{
	double a[N << 3];
	inline void modify(int l,int r,int x,double k,int pos)
	{
		a[pos] = max(a[pos],k);
		if(l == r) return;
		int mid = (l + r) >> 1;
		if(x <= mid) modify(l,mid,x,k,pos << 1);
		else modify(mid + 1,r,x,k,pos << 1 | 1);
	}
	inline double query(int l,int r,int L,int R,int pos)
	{
		if(L > R) return -inf;
		if(L <= l && r <= R) return a[pos];
		int mid = (l + r) >> 1; double ret = -inf;
		if(L <= mid) ret = max(ret,query(l,mid,L,R,pos << 1));
		if(R > mid) ret = max(ret,query(mid + 1,r,L,R,pos << 1 | 1));
		return ret;
	}
	inline void clear() {fill(a,a + (N << 3),-inf);}
}t;
int f[N]; 
struct Node{
	int dfn,siz,dep,mxd,son,fa,top;
	double dis;
}a[N];
inline void dfs1(int x,int last)
{
	a[x].dep = a[last].dep + 1;
	a[x].siz = 1;
	a[x].fa = last;
	a[x].mxd = 0;
	for(int i = head[x];i;i = e[i].next)
	{
		int to = e[i].v;
		if(to == last) continue;
		a[to].dis = a[x].dis + e[i].w;
		dfs1(to,x);  
		a[x].siz += a[to].siz;
		if(a[to].mxd + 1 > a[x].mxd) a[x].mxd = a[to].mxd + 1,a[x].son = to;
	}
} 
inline void dfs2(int x,int last)
{
	a[x].dfn = ++tot;
	f[x] = a[x].dfn;
	if(a[x].son) {a[a[x].son].top = a[x].top; dfs2(a[x].son,x);}
	for(int i = head[x];i;i = e[i].next)
	{
		int to = e[i].v;
		if(to == last || to == a[x].son) continue;
		a[to].top = to;
		dfs2(to,x);
	}
}
inline void add(int x,int y,int z)
{
	++tot;
	e[tot].v = y;
	e[tot].w = z;
	e[tot].next = head[x];
	head[x] = tot;
	++tot;
	e[tot].v = x;
	e[tot].w = z;
	e[tot].next = head[y];
	head[y] = tot;
}
inline void dfs3(int x,int last)
{
	t.modify(1,N,f[x],a[x].dis - mid * a[x].dep,1);
	if(a[x].son) dfs3(a[x].son,x);
	for(int i = head[x];i;i = e[i].next)
	{
		int to = e[i].v;
		if(to == last || to == a[x].son) continue;
		dfs3(to,x);
		for(int j = 1;j <= a[to].mxd + 1;j++)
		{
			double vto = t.query(1,N,f[to] + j - 1,f[to] + j - 1,1);
			if(j <= U)
				ans = max(ans,vto + t.query(1,N,f[x] + max(1ll,L - j),f[x] + min(U - j,a[x].mxd),1) - 2 * (a[x].dis - mid * a[x].dep));
			tmp[j] = vto;
		}
		for(int j = 1;j <= a[to].mxd + 1;j++) t.modify(1,N,f[x] + j,tmp[j],1);
	}
	ans = max(ans,t.query(1,N,f[x] + L,f[x] + min(U,a[x].mxd),1) - (a[x].dis - mid * a[x].dep));
}
inline bool ck()
{
	t.clear();
	ans = -inf;
	dfs3(1,0);
	return ans >= 0;
}
signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	cin>>L>>U;
	for(int i = 1,x,y,z;i <= n - 1;i++)
	{
		cin>>x>>y>>z;
		add(x,y,z);
	}
	tot = 0;
	a[0].dep = -1; a[0].dis = 0;
	dfs1(1,0);
	dfs2(1,0);
	double l = 0,r = 1e6;
	while(l + eps < r)
	{
		mid = (l + r) / 2;
		if(ck()) l = mid;
		else r = mid;
	}
	cout<<fixed<<setprecision(3)<<l;
	return 0;
}

本栏目推荐文章
• uniDBtree树形显示
• 动态代理
• 整数的划分（递归或动态规划）
• 动态代理
• 【C语言】动态内存申请，堆空间与栈空间差异
• dp优化-wqs二分
• 海亮01/12dp专题
• 实时数据流无忧：用 SpringBoot 和 SSE 打造动态前端更新的终极指南
• 使用iviewUI动态添加、删除输入框及做对应的判断
• CS5340国产替代 DP8340 192KHz 双声道输入24 位AD 转换器芯片

树形 动态 dp树形 动态dp 树形dp 树形 专题dp 树形369 dfs dp 树形 笔记dp 动态dp 树形apple tree dp 树形 习题dp 树形 动态 树形 舞会 上司 动态