树上dfs序小专题
说在前面的
和欧拉序都是非常有力的工具，我们应该熟练的运用两者。而且
序也不必局限于树上的
序，其实一般图也有
序，有兴趣的朋友可以参考
算法。
- 以下的
序，全部指树上的
- 以下的
，全部指以
为根，子树的大小。
dfs 序
引入
如何判断 是否有所属关系，也就是
，多次询问。我们发现我们并不能把每个节点的
记录下来，这使我们不太好查询是否
。
- 我们可以考虑模拟
性质
的性质是非常多，而且非常重要的。这里选取一些常用的进行讲解。
- 一个子树的
个元素结束，这些元素全是属于
欧拉序(括号序列)
这个欧拉序和 序其实有非常多的共同点，在构造时的唯一区别是，
是在只第一次访问时加入数组中。而欧拉序还要在回溯时，把该节点压入数组。如果我们把第一次访问，当作是加入左括号
，回溯看作是加入右括号
。那么最后
遍历完整个树，最后得到的就是一个括号序列。
性质
由于欧拉序维护了出栈的标记，所以相比 序，更加强大，维护的东西也更加多。
每个节点会出现两次。因为入栈出栈都维护了。
相邻两个节点的深度相差
。
可以维护树上路径。这个就比较有意思了。我们把第一次进入数组的位置命名为
，第二次称之为
。那么
是要分类讨论的。
。那么
从
中只出现了一次的元素。为什么是只出现一次呢，由于
所以出现两次的，是其它子树的元素，与
。那么
组成的。出现两次的元素一定是
还没遍历完，所以
还没有进入数组，所以要把
- 维护祖先儿子关系。同
。
例题
出于写博客服务于大家和自己，这里先将一点关于 序的基础题，最后再讲讲牛客的例题（谢谢理解）。
Tree Queries
题意
给你一个以 为根的有根树，每回询问
个节点
。求出是否有一条以根节点为一端的链，使得询问的每个节点到此链的距离均
。只需输出可行性, 无需输出方案。
分析
无论是哪种方案，想要使链到节点的距离 。那么只有三种可能。
- 经过父亲。
- 经过自己。
- 经过一个直接的儿子。
但是我们发现这三种其实都必须经过父亲。所以把 的父亲的
序由小到大排序，最后判断后一个是不是当前节点的儿子，就可以了，这个可以通过
序做到。复杂度为
。
代码
#include<bits/stdc++.h>
using namespace std;
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch=getchar();}
return f?-x:x;
}
const int N = 2e5+100;
int n,m,dep[N],fa[N],dfn[N],Id,st[N],si[N];
vector<int> G[N];
bool cmp(int x,int y) {return dep[x] < dep[y];}
void dfs(int x,int f,int de) {
dep[x] = de;dfn[x] = ++Id;si[x]=1;fa[x] = f;
for(auto y:G[x]) {if(y == f) continue;dfs(y,x,de+1);si[x]+=si[y];}
}
int main()
{
n = read();m = read();
for(int i = 1;i < n;i++) {
int x = read(),y = read();
G[x].push_back(y);G[y].push_back(x);
}
dfs(1,1,1);
while(m--) {
int sum = read(),check = 0;
for(int i = 1;i <= sum;i++) st[i] = fa[read()];
sort(st+1,st+1+sum,cmp);
for(int i = 2;i <= sum;i++) {
if(dfn[st[i]] >= dfn[st[i-1]] && dfn[st[i]] <= dfn[st[i-1]] + si[st[i-1]] - 1) continue;
check = 1;
}
!check?puts("Yes"):puts("No");
}
}Military Problem
分析
这个就是模拟 的过程就行了，判断可以直接输出
序对应的元素。输出前判断一下
于
的关系就好了。小细节，如果要用链式前向星存边，那么根据遍历顺序，应该倒着建边，这个稍微分析一下就好了。最后总复杂度为
。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1000;
int ecnt,si[N],id[N],pos[N],head[N],n,Id,to[N];
struct Edge {int to,nxt;}e[N];
int read() {int x;scanf("%d",&x);return x;}
void add(int x,int y) {e[++ecnt].to = y;e[ecnt].nxt = head[x];head[x] = ecnt;}
void dfs(int x) {
pos[id[x] = ++Id] = x;si[x] = 1;
for(int i = head[x];i;i=e[i].nxt) dfs(e[i].to),si[x] += si[e[i].to];
}
int main() {
n = read();int Q = read();
for(int i = 2,fa;i <= n;i++) to[i] = read();
for(int i = n;i > 1;i--) add(to[i],i);
dfs(1);
while(Q--) {
int rt = read(),k = read();
if(si[rt] < k) puts("-1");
else printf("%d\n",pos[id[rt] + k - 1]);
}
}选点
分析
不太一样的 序，但是核心思想没有区别。由于我们选出来的点要满足
。那么我们可以先遍历
这样的顺序遍历，这样把树映射到序列上，这样问题就形式化了。求问一个序列的最长上升子序列。这样就可以随便做了，可以用数据结构优化一下，总复杂度为
。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1000;
int read() {int x;scanf("%d",&x);return x;}
int n,lc[N],rc[N],id[N],Id,pos[N],f[N],ans,w[N],t[N];
void dfs(int x) {
pos[id[x] = ++Id] = x;
if(rc[x]) dfs(rc[x]);if(lc[x]) dfs(lc[x]);
}
void upd(int x,int v) {for(int i = x;i <= n;i += i & -i) t[i] = max(t[i],v);}
int ask(int x) {int tot = 0;for(int i = x;i;i -= i & -i) tot = max(tot,t[i]);return tot;}
int res[N];
int main() {
n = read();
for(int i = 1;i <= n;i++) res[i] = w[i] = read();
for(int i = 1;i <= n;i++) lc[i] = read(),rc[i] = read();
sort(res + 1,res + 1 + n);
int cnt = unique(res + 1,res + 1 + n) - res - 1;
for(int i = 1;i <= n;i++) w[i] = lower_bound(res + 1,res + cnt + 1,w[i]) - res;
dfs(1);
for(int i = 1;i <= n;i++) {
f[i] = ask(w[pos[i]] - 1) + 1;
ans = max(f[i],ans);
upd(w[pos[i]],f[i]);
}
printf("%d\n",ans);
return 0;
}Tree Requests
题意
给定一个以 为根的
个节点的树，每个点上有一个字母
到
，每次询问
，查询以
为根的子树内深度为
的节点上的字母重新排列之后是否能构成回文串。
分析
关于这题，我并没有非常好的基于 序的做法，抱歉。这里提供一种树上启发式合并的做法。构成回文串的字母应该满足
。
表示
这个字符出现的次数。那么根据每个元素只会在跳轻边时合并，而任何一个节点到根路径上只有
条轻边，那么总复杂度为
。
代码
#include<bits/stdc++.h>
using namespace std;
const int M = 5e5+1000;
struct Query{
int de,id;
};
int n,m;
vector<int> G[M];
vector<Query> Q[M];
int L[M],R[M],id[M],T;
int dep[M],son[M],si[M];
int check[M],ans[M];
char A[M];
void dfs(int u,int d) {
L[u] = ++T;dep[u] = d;
id[T] = u;son[u] = 0;si[u] = 1;
for(int i = 0;i < G[u].size();i++) {
int v = G[u][i];
dfs(v,d+1);
if(si[v]>si[son[u]]) son[u] = v;
si[u] += si[v];
}
R[u] = T;
}
void add_point(int x) {
int r = A[x] - 'a',d = dep[x];
check[d] ^= (1<<r);
}
void add_tree(int x) {
for(int i = L[x];i <= R[x];i++) add_point(id[i]);
}
void solve(int x) {
for(int i = 0;i < G[x].size();i++) {
int y = G[x][i];
if(y == son[x]) continue;
solve(y);add_tree(y);
}
if(son[x]) solve(son[x]);
for(int i = 0;i < G[x].size();i++) {
int y = G[x][i];
if(y == son[x]) continue;
add_tree(y);
}
add_point(x);
for(int i = 0;i < Q[x].size();i++) {
int d = Q[x][i].de,r = check[d],id = Q[x][i].id;
ans[id] = (r==(r&-r));
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 2,f;i <= n;i++) {
scanf("%d",&f);
G[f].push_back(i);
}
dfs(1,1);
scanf("%s",A+1);
for(int i = 1;i <= m;i++) {
int x,d;
scanf("%d%d",&x,&d);
Q[x].push_back((Query){d,i});
}
solve(1);
for(int i = 1;i <= m;i++) {
if(ans[i]) puts("Yes");
else puts("No");
}
return 0;
}Colorful Tree
题意
支持两个操作。改变一个节点的颜色。查询由一种颜色构成的最小生成树的价值。
分析
我们对于一个树上选一些节点使他们的联通的代价最小。这个问题，我们可以按 序由大到小排序，这样依次联接是没有重复路径的。这个可以手摸一下，也可以通过
的性质得到。那么我们现在要处理的就是，如果删除和添加一个节点。我们考虑到，删除一个节点，那么这个节点左右两个元素的
序仍然是连续的，所有我们可以考虑一个元素的贡献，为
。那么我们就开个平衡树维护一下这个颜色的所有元素，动态的维护答案就好了。总的复杂度为
。
- 小技巧，树上的节点
的简单路径只有一条，其长度为
。
代码
#include<bits/stdc++.h>
using namespace std;
#define It set<int>::iterator
const int N = 1e5 + 1000;
int read() {int x;scanf("%d",&x);return x;}
struct Edge {int to,nxt;}e[N<<1];
int id[N],rid[N],col[N],Id,head[N],fa[N][21],dep[N],n,ecnt;
void add(int x,int y) {e[++ecnt] = (Edge){y,head[x]};head[x] = ecnt;}
int lca(int idx,int idy) {
int x = rid[idx],y = rid[idy];
if(dep[x] < dep[y]) swap(x,y);
int k = dep[x] - dep[y];
for(int i = 20;~i;i--) if((k >> i) & 1) x = fa[x][i];
if(x == y) return x;
for(int i = 20;~i;i--) if(fa[x][i] ^ fa[y][i]) x = fa[x][i],y = fa[y][i];
return fa[x][0];
}
int dis(int idx,int idy) {
int x = rid[idx],y = rid[idy];
return (dep[x] + dep[y] - 2 * dep[lca(idx,idy)]);
}
void dfs(int x,int f) {
fa[x][0] = f;rid[id[x] = ++Id] = x;
for(int i = 1;i <= 20;i++) fa[x][i] = fa[fa[x][i-1]][i-1];
for(int i = head[x];i;i=e[i].nxt) {
int y = e[i].to;if(y == f) continue;
dep[y] = dep[x] + 1;dfs(y,x);
}
}
struct MST {
set<int> s;int sum;
void add(int x) {
s.insert(x);It it = s.find(x);
int L = 0,R = 0;
++it;if(it != s.end()) R = *it;
--it;if(it != s.begin()) --it ,L = *it;
if(L && R) sum -= dis(L,R);
if(L) sum += dis(L,x);if(R) sum += dis(x,R);
}
void del(int x) {
It it = s.find(x);
int L = 0,R = 0;
++it;if(it != s.end()) R = *it;
--it;if(it != s.begin()) --it ,L = *it;
if(L && R) sum += dis(L,R);
if(L) sum -= dis(L,x);if(R) sum -= dis(x,R);
it = s.find(x);s.erase(it);
}
int ans() {return (sum + dis(*s.begin(),*s.rbegin())) / 2;}
}A[N];
int main() {
n = read();
for(int i = 1,x,y;i < n;i++) {
x = read();y = read();
add(x,y);add(y,x);
}
dfs(1,0);
for(int i = 1;i <= n;i++) {
col[i] = read();A[col[i]].add(id[i]);
}
int Q = read();
while(Q--) {
char ch[10];scanf("%s",ch + 1);
if(ch[1] == 'U') {
int x = read(),y = read();
A[col[x]].del(id[x]);
col[x] = y;
A[col[x]].add(id[x]);
}
else {
int x = read();
if(A[x].s.empty()) puts("-1");
else printf("%d\n",A[x].ans());
}
}
}求和 & Propagating tree
由于这两道题，没有什么本质上的区别。这里就把思路呈现出来。
分析
要求维护两个操作，查询单点和修改子树。我们可以直接用线段树在 序乱搞，也可以转化为差分之后用树状数组维护。而
这道题，我们用奇偶分个组，也就做完了。
- 这里有个小技巧，一般对于链上查询，都可以差分成子树修改。虽然这里没有用到，但是我认为这个还是非常重要的。因为维护
代码
#include<bits/stdc++.h> using namespace std; const int N = 1e6 + 1000; int ecnt,L[N],R[N],head[N],n,rt,Id; struct Edge {int to,nxt;}e[N << 1]; int read() {int x;scanf("%d",&x);return x;} void add(int x,int y) {e[++ecnt].to = y;e[ecnt].nxt = head[x];head[x] = ecnt;} void dfs(int x,int f) { L[x] = ++Id; for(int i = head[x];i;i=e[i].nxt) if(e[i].to ^ f) dfs(e[i].to,x); R[x] = Id; } int val[N],t[N << 2]; void update(int u,int l,int r,int pos,int k) { if(l == r) {t[u] += k;return;} int mid = l + r >> 1; if(pos <= mid) update(u << 1,l,mid,pos,k); else update(u << 1 | 1,mid + 1,r,pos,k); t[u] = t[u << 1] + t[u << 1 | 1]; } int ask(int u,int l,int r,int L,int R) { if(l > R || r < L) return 0; if(L <= l && r <= R) return t[u]; int mid = l + r >> 1; return (ask(u << 1,l,mid,L,R) + ask(u << 1 | 1,mid + 1,r,L,R)); } int main() { n = read();int Q = read();rt = read(); for(int i = 1;i <= n;i++) val[i] = read(); for(int i = 1,a,b;i < n;i++) { a = read();b = read(); add(a,b);add(b,a); } dfs(rt,0); for(int i = 1;i <= n;i++) update(1,1,n,L[i],val[i]); while(Q--) { int opt = read(); if(opt == 2) { int x = read(); printf("%d\n",ask(1,1,n,L[x],R[x])); } else { int x = read(),y = read(); update(1,1,n,L[x],y); } } } #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 1000; int ecnt,L[N],R[N],head[N],n,Id; bool col[N]; struct Edge {int to,nxt;}e[N << 1]; int read() {int x;scanf("%d",&x);return x;} void add(int x,int y) {e[++ecnt].to = y;e[ecnt].nxt = head[x];head[x] = ecnt;} void dfs(int x,int f,int c) { L[x] = ++Id;col[x] = c; for(int i = head[x];i;i=e[i].nxt) if(e[i].to ^ f) dfs(e[i].to,x,1 - c); R[x] = Id; } int val[N]; struct SegmentTree { int t[N << 2]; void update(int u,int l,int r,int pos,int k) { if(l == r) {t[u] += k;return;} int mid = l + r >> 1; if(pos <= mid) update(u << 1,l,mid,pos,k); else update(u << 1 | 1,mid + 1,r,pos,k); t[u] = t[u << 1] + t[u << 1 | 1]; } int ask(int u,int l,int r,int L,int R) { if(l > R || r < L) return 0; if(L <= l && r <= R) return t[u]; int mid = l + r >> 1; return (ask(u << 1,l,mid,L,R) + ask(u << 1 | 1,mid + 1,r,L,R)); } }T[2]; int main() { n = read();int Q = read(); for(int i = 1;i <= n;i++) val[i] = read(); for(int i = 1,a,b;i < n;i++) { a = read();b = read(); add(a,b);add(b,a); } dfs(1,0,1); n++; while(Q--) { int opt = read(); if(opt == 2) { int x = read(); printf("%d\n",val[x] + T[col[x]].ask(1,1,n,1,L[x]) - T[1-col[x]].ask(1,1,n,1,L[x])); } else { int x = read(),y = read(); T[col[x]].update(1,1,n,L[x],y); T[col[x]].update(1,1,n,R[x] + 1,-y); } } }
[USACO19DEC]Bessie's Snow Cow P
个人觉得不错的一道题目，比较综合，要考虑 序上的差分，建议画个图理解一下。
分析
我们查询答案时，我们有两种答案。一是，全部覆盖了子树的答案，二是，只覆盖了一部分子树的答案。所以我们可以对这两种答案分别开一个树状数组维护。而修改操作就可以对每个颜色开一个 ，每次修改到他的父亲，那么它的贡献就可以减去。那么总复杂度为
。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100,inf = 0x3f3f3f3f;
#define ll long long
int read() {int x;scanf("%d",&x);return x;}
struct Edge {int to,nxt;}e[N << 1];
set<int> s[N];
#define It set<int>::iterator
int n,head[N],ecnt,id[N],rid[N],Id,si[N];
void add(int x,int y) {e[++ecnt]=(Edge){y,head[x]};head[x] = ecnt;}
struct Bit {
ll t[N];
void upd(int a,ll d) {for(int i = a;i <= n;i += i & -i) t[i] += d;}
ll ask(int a) {ll tot = 0;for(int i = a;i;i -= i & -i) tot += t[i];return tot;}
}A,B;
void dfs(int x) {
rid[id[x] = ++Id] = x;si[x] = 1;for(int i = head[x];i;i = e[i].nxt) {
int y = e[i].to;if(id[y]) continue;dfs(y); si[x] += si[y];
}
}
void upd(int x,int d) {
// cout << x << " " << d << endl;
A.upd(id[x],d);
A.upd(id[x] + si[x],-d);
B.upd(id[x],si[x] * d);
}
bool in(int a,int b) {return si[a] + id[a] <= si[b] + id[b];}
int main() {
n = read();int Q = read();
for(int i = 1,a,b;i < n;i++) {
a = read();b = read();
add(a,b);add(b,a);
}
dfs(1);
// cout << "debug1 " << endl;
while(Q--) {
int opt = read();
if(opt == 1) {
int x = read(),y = read();
It it = s[y].lower_bound(id[x]);
if(it != s[y].begin()) {
It itl = it;itl--;
if(in(x,rid[*itl])) continue;
}
while(it != s[y].end() && (*it) <= si[x] + id[x] - 1) {
// cout << (*it) << endl;
upd(rid[(*it)],-1);s[y].erase(it++);
}
s[y].insert(id[x]);upd(x,1);
}
else {
int x = read();
ll ans = si[x] * A.ask(id[x]) + B.ask(id[x] + si[x] - 1) - B.ask(id[x]);
printf("%lld\n",ans);
}
}
}结语
序强大在于它将一个树转化为一个序列，使我们的操作更加简便。其实还有许多题目可以用到
序，而且像树链剖分这种算法就是基于
序实现的。反正就是很重要了。
字节跳动公司氛围 550人发布
投递蚂蚁集团等公司10个岗位 >