Dominant Indices【模板】长链剖分

本文主要是介绍Dominant Indices【模板】长链剖分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Dominant Indices总题单链接

对比重链剖分和长链剖分

什么是重链剖分：根据子树的大小将树拆成多条互不相交的链。

什么是长链剖分：根据字数的深度将树拆成多条互不相交的链。

重链剖分中的重儿子：子树大小最大的儿子。

长链剖分中的重儿子：子树深度最深的儿子。

重链剖分的作用：找 $L C A$ ，结合线段树维护书上路劲查询和修改。

长链剖分的作用：优化和深度有关的树上 $D P$ ，尤其是子树合并类的 $D P$ 。

可以发现重链剖分和长链剖分的主要区别就是一个注重大小，一个注重深度。

怎么对树进行长链剖分

深搜就行，看代码理解。

$l e n [p]$ 就是 $p$ 子树的最深的节点的深度，即子树的最大深度。

void dfs_build(ll fa,ll p){for(ll v:eg[p]){if(v==fa)continue;dfs_build(p,v);if(len[son[p]]<len[v])son[p]=v;}len[p]=len[son[p]]+1;
}

模板题讲解

看到题目，我们可以想到一个非常基础的子树合并 $D P$ 。

设 $d p [i] [j]$ 为在 $i$ 点的子树中，距离 $i$ 为 $j$ 的点有多少个。

这样做的时间复杂度和空间复杂度都是 $O(N^2)$ 的，需要优化。

优化的关键点——继承，在同一条长链上时，父节点可以直接继承其重儿子的 $d p$ 值，这一过程是 $O (1)$ 的。

怎么 $O (1)$ 继承呢？这就要用到一个同样非常巧妙的技巧——空间共享！先来看看朴素方法是怎么 $O (N)$ 继承的。枚举 $i$ ， $d p [u] [i] = d p [v] [i - 1]$ 。而空间共享，就是直接将 $d p [u] [i]$ 和 $d p [v] [i - 1]$ 用数组中的同一个位置记录，这样在修改 $d p [v] [i - 1]$ 时， $d p [u] [i]$ 就会被自动修改。

具体实现时，先用定义一个数组用来申请空间，然后用一个指针指向这个数组的开头，对于每条链，分配的空间大小就是链的长度。这个不好直接理解，建议看代码的指针部分。

不是同一条链的情况，就暴力合并。

模板题代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;ll n,ans[1000005];
vector<ll>eg[1000005];
ll len[1000005],son[1000005];
ll buf[1000005],*f[1000005],*t=buf;void dfs_build(ll fa,ll p){for(ll v:eg[p]){if(v==fa)continue;dfs_build(p,v);if(len[son[p]]<len[v])son[p]=v;}len[p]=len[son[p]]+1;
}void dfs_dp(ll fa,ll p){f[p][0]=1;if(son[p]){f[son[p]]=f[p]+1;dfs_dp(p,son[p]);ans[p]=ans[son[p]]+1;}for(ll v:eg[p]){if(v==fa||v==son[p])continue;f[v]=t;t+=len[v];dfs_dp(p,v);for(ll i=1;i<=len[v];i++){f[p][i]+=f[v][i-1];if((f[p][i]>f[p][ans[p]])||(f[p][i]==f[p][ans[p]]&&i<ans[p]))ans[p]=i;}}if(f[p][ans[p]]==1)ans[p]=0;
} signed main(){ios::sync_with_stdio(false);cin>>n;for(ll i=1;i<n;i++){ll x,y;cin>>x>>y;eg[x].push_back(y);eg[y].push_back(x);}dfs_build(0,1);f[1]=t;t+=len[1];dfs_dp(0,1);for(ll i=1;i<=n;i++)cout<<ans[i]<<endl;return 0;
}