DFS序专题
NC13611 https://ac.nowcoder.com/acm/problem/13611
题意：要求树上任意两点相同颜色之间的路径上的点也是相同颜色，k种颜色，求方案数
Solution：原问题等价于将树分割成若干连通块且相互之间颜色不同
其实是道数论题。 题意可以转化为将树分割为不超过 \(k\) 个连通块，每个连通块颜色不同。若将树分割为 \(i\) 个连通块，则需要删去 \(i-1\) 条边，故方案数为 \(\mathrm{C}_{n-1}^{i-1}\) 。同时，要从 \(k\) 种颜色中选出 \(i\) 中颜色染色，而且是有顺序的，故方案数为 \(\mathrm{A}_{k}^{i}\) 。 综上，总的方案数为： \(ans= \sum_{i=1}^{\min(n,k)}\mathrm{C}_{n-1}^{i-1}\mathrm{A}_{k}^{i}\) 可以线性求逆元，枚举 \(i\) 实现。 时间复杂度：\(O(n)\) 。
Code
void init(int n) {
inv[0]=inv[1]=1;
for (int i=2;i<=n;i++) inv[i] = (mod-mod/i)*inv[mod%i]%mod;
for (int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
finv[1] = f[1] = finv[0] = f[0] = 1;
for (int i = 2; i <= n; i++) finv[i] = finv[i - 1] * inv[i] % mod;
for (int i = 2; i <= n; i++) f[i] = f[i - 1] * i % mod;
}
int C(int a,int b){
if(a==0||b==0)return 1;
return f[a]*finv[a-b]%mod*finv[b]%mod;
}
int A(int a,int b){
if(a==0||b==0)return 1;
return f[a]*finv[a-b]%mod;
}
void solve(){
int k;cin>>n>>k;
init(n);
for(int i=1;i<=n-1;i++){
int u,v;cin>>u>>v;
}
int ans=0;
for(int i=1;i<=min(n,k);i++){
ans+=C(n-1,i-1)*A(k,i)%mod;
ans%=mod;
}
cout<<ans<<endl;
}
本题如果不考虑组合数学，还可以从dp的角度考虑，我们先做一遍dfs序然后在序列上考虑。用f[i] [j] 表示树上dfs序的前i个点用了j种颜色的方法数$ f[i] [j] = f[i-1] [j] + f[i-1] [j-1] \times (k-j+1) $
- 对于当前节点，如果选之前的颜色那么只能和父节点颜色相同，和其他点颜色相同也会必经父节点。
- 如果不选之前的颜色，则有剩余没被选的颜色种选择
dfs序模板题
https://codeforces.com/problemset/problem/1006/E
题意：每次静态查询某个节点子树第k个被访问的点，访问顺序是以编号小的优先。
int l[N];
int r[N];
vector<int>e[N];
int idx=0;
int dfn[N];
int rk[N];
void dfs(int u,int fa){
l[u]=++idx;
dfn[u]=idx;
rk[idx]=u;
for(auto v:e[u]){
if(v==fa)continue;
dfs(v,u);
}
r[u]=idx;
}
void solve(){
cin>>n>>m;
for(int i=2;i<=n;i++){
int x;cin>>x;
e[x].push_back(i);
}
dfs(1,0);
for(int i=1;i<=m;i++){
int u,k;cin>>u>>k;
int len=r[u]-l[u]+1;
if(len<k)cout<<-1<<endl;
else {
int pos=l[u]+k-1;
cout<<rk[pos]<<endl;
}
}
}
NC22494
链接：https://ac.nowcoder.com/acm/problem/22494
来源：牛客网
题面：有一棵n个节点的二叉树，1为根节点，每个节点有一个值wi。现在要选出尽量多的点。 对于任意一棵子树，都要满足： 如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大； 如果在左子树选了一个点，在右子树中选的其他点要比它小。
题意：选的点需要满足点权值根<右<左，我们考虑dfs序按照这个偏序关系进行从而得到一个序列，所以我们只需要找到LIS,由于数据范围是1e5,所以我们需要使用单调栈加二分的方式去找到最长严格上升子序列
int a[N];
int lc[N],rc[N];
int ans[N];int idx=0;
void dfs(int u){
if(u==0)return ;
ans[++idx]=u;
dfs(rc[u]);
dfs(lc[u]);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
cin>>lc[i]>>rc[i];
}
dfs(1);
vector<int>v;
for(int i=1;i<=n;i++){
int id=ans[i];
v.push_back(a[id]);
}
vector<int>ls;
for(int i=0;i<(int)v.size();i++){
//cerr<<v[i]<<endl;
if(ls.empty()||v[i]>ls.back())ls.push_back(v[i]);
else {
int pos=lower_bound(ls.begin(),ls.end(),v[i])-ls.begin();
ls[pos]=v[i];
}
}
int res=ls.size();
//res++;
cout<<res<<endl;
}
开始利用dfs序进行树上常规数据结构操作
链接：https://ac.nowcoder.com/acm/problem/204871
已知有 \(n\) 个节点，有 \(n-1\) 条边，形成一个树的结构。 给定一个根节点 \(k\)，每个节点都有一个权值，节点i的权值为 \(v_i\)。 给 \(m\) 个操作，操作有两种类型：
- 1 a x ：表示将节点 \(a\) 的权值加上 \(x\)
- 2 a ：表示求 \(a\) 节点的子树上所有节点的和（包括 \(a\) 节点本身）
题意：进行在线的单点修改和子树点权和查询
Solution：利用dfs序转到序列问题，显然可以用树状数组维护
vector<int>e[N];
int l[N],r[N];
int idx=0;
void dfs(int u,int fa){
l[u]=++idx;
for(auto v:e[u]){
if(v==fa)continue;
dfs(v,u);
}
r[u]=idx;
}
void solve(){
cin>>n;
cin>>m;
int root;cin>>root;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n-1;i++){
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
Fenwick<int>c(n+1);
dfs(root,0);
for(int i=1;i<=n;i++){
c.add(l[i],a[i]);
}
for(int i=1;i<=m;i++){
int op;cin>>op;
if(op==1){
int id,val;
cin>>id>>val;
c.add(l[id],val);
}
else {
int pos;cin>>pos;
int ql=l[pos],qr=r[pos];
int ans=c.rangeSum(ql-1,qr);
cout<<ans<<endl;
}
}
}
考察离线思想的dfs序上树状数组
链接：https://ac.nowcoder.com/acm/problem/23051
华华和月月一起维护了一棵动态有根树，每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0 。接下来有两种操作：
-
操作 1：输入格式\(1\ i\)，表示月月氪金使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1（也可以理解为，当前是第几个操作 1，新节点的编号就是多少）。
-
操作 2：输入格式 \(2 \ i \ a\)，表示华华上线做任务使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。 但是月月有时会检查华华有没有认真维护这棵树，会作出询问：
-
询问 3：输入格式\(3\ i\)，华华需要给出 i 节点此时的权值。