dfs序专题

自用笔记算法

dfs序专题

HDU 3887

题目要求

给出一棵树 root为p
对于每个结点输出它的子树中编号比它小的结点个数

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,p,step;
vector<int>e[maxn];
int in[maxn],out[maxn];
int tree[maxn];
void add(int x,int val){
    while(x<=n){
        tree[x]+=val;
        x+=x&(-x);
    }
}
int sum(int x){
    int res=0;
    while(x){
        res+=tree[x];
        x-=x&(-x);
    }
    return res;
}
void dfs(int x,int fa){
    in[x]=step;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa) continue;
        step++;
        dfs(next,x);
    }
    out[x]=step;
}
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&p)!=EOF){
        if(n==0 && p==0) break;
        for(int i=0;i<=n;i++) e[i].clear();
        mm(in,0),mm(out,0),mm(tree,0); 
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        step=1;
        dfs(p,0);
        for(int i=1;i<=n;i++){
            int ans=sum(out[i])-sum(in[i]-1);
            if(i==1) printf("%d",ans);
            else printf(" %d",ans);
            add(in[i],1);
        }
        printf("\n");
    }
    return 0;
}

思路

dfs+树状数组
对于子树的操作 可以联想到dfs序
也运用到贪心的思想
从结点1开始每次进行sum操作后把该点加入到tree中 从结点小的开始依次插入可以确保答案正确

HDU 5692

题目要求

百度科技园内有n个零食机，零食机之间通过n−1条路相互连通。每个零食机都有一个值v，表示为小度熊提供零食的价值。
由于零食被频繁的消耗和补充，零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。
另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。
为小度熊规划一个路线，使得路线上的价值总和最大。

输入数据第一行是一个整数T(T≤10)，表示有T组测试数据。
对于每组数据，包含两个整数n,m(1≤n,m≤100000)，表示有n个零食机，m次操作。
接下来n−1行，每行两个整数x和y(0≤x,y<n)，表示编号为x的零食机与编号为y的零食机相连。
接下来一行由n个数组成，表示从编号为0到编号为n−1的零食机的初始价值v(|v|<100000)。
接下来m行，有两种操作：0 x y，表示编号为x的零食机的价值变为y；1 x，表示询问从编号为0的零食机出发 必须经过编号为x零食机的路线中 价值总和的最大值。
本题可能栈溢出，辛苦同学们提交语言选择c++，并在代码的第一行加上：

#pragma comment(linker, “/STACK:1024000000,1024000000”)

对于每组数据，首先输出一行”Case #?:”，在问号处应填入当前数据的组数，组数从1开始计算。
对于每次询问，输出从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const int maxn = 100000+7;
const LL INF=(LL)1e18;
LL dis[maxn],a[maxn];
LL sum[maxn<<2],lazy[maxn<<2];
vector<int>e[maxn];
int n,m,in[maxn],out[maxn],id[maxn],step;
void init(){
	for(int i=0;i<=n;i++) e[i].clear();
	mm(a,0),mm(sum,0),mm(lazy,0),mm(dis,0);
	mm(in,0),mm(out,0),mm(id,0);
	step=1;
}
void dfs(int x,int fa){
	in[x]=step;
	id[step]=x;
	int len=e[x].size();
	for(int i=0;i<len;i++){
		int next=e[x][i];
		if(next==fa) continue;
		step++;
		dis[next]=dis[x]+a[next];
		dfs(next,x);
	}
	out[x]=step;
}
void push_up(int rt){
	sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
void push_down(int rt){
	if(lazy[rt]){
		sum[rt<<1]+=lazy[rt];
		sum[rt<<1|1]+=lazy[rt];
		lazy[rt<<1]+=lazy[rt];
		lazy[rt<<1|1]+=lazy[rt];
		lazy[rt]=0;
	}
}
void build(int rt,int l,int r){
	if(l==r){
		sum[rt]=dis[id[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	push_up(rt);
}
void update(int rt,int l,int r,int val,int L,int R){
	if(l>=L && r<=R){
		lazy[rt]+=val;
		sum[rt]+=val;
		return;
	}
	int mid=(l+r)>>1;
	push_down(rt);
	if(mid>=L) update(lson,val,L,R);
	if(mid<R) update(rson,val,L,R);
	push_up(rt);
}
LL query(int L,int R,int rt,int l,int r){
	if(l>=L && r<=R) return sum[rt];
	push_down(rt);
	int mid=(l+r)>>1;
	LL ans=-INF;
	if(mid>=L) ans=max(ans,query(L,R,lson));
	if(mid<R) ans=max(ans,query(L,R,rson));
	return ans;
}
int flag=1;
int main(){
//	freopen("input.txt","r",stdin);
	int t; scanf("%d",&t);
	while(t--){
		cout<<"Case #"<<flag++<<":"<<endl;
		scanf("%d%d",&n,&m);
		init();
		for(int i=1;i<n;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			u++,v++;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		dis[1]=a[1];
		dfs(1,0);
		build(1,1,n);
		while(m--){
			int op; scanf("%d",&op);
			if(op==0){
				int x,y; scanf("%d%d",&x,&y);
				x++;
				update(1,1,n,y-a[x],in[x],out[x]);
				a[x]=y;
			}
			else{
				int x; scanf("%d",&x);
				x++;
				LL ans=query(in[x],out[x],1,1,n);
				printf("%lld\n",ans);
			}
		}
	}
	return 0;
}

思路

dfs+线段树
题中需要求必须进过某点x 所以问题转换为求x子树中的结点到根节点的最大权值和
所以进一步转换为dfs序 用线段树维护权值和的最大值
因为这里的单点修改会影响到整棵子树进一步影响到整个线段树 所以实质是区间修改
本题的下标从0开始 方便计算我们全部+1
对于替换操作 实际上就是加上y-a[x] id数组记录的是序列是l的结点编号是多少 进一步取到dis的权值和
在dfs中可以顺带把dis求出(所有结点到根节点的权值和) 这里需要注意dis[1]初始化为a[1]
本题的2个注意点：
1.宏定义里mid不能写成m 会和原来的m参数交互
2.注意LR和lr的次数 因为粗心写反了调了1个小时

poj 3321(单点01修改+求子树的权值和)

转跳链接

fzu 2277(子树点权区间修改+单点查询)

转跳链接

HDU 5468

题目要求

一棵树 每个点都有一个点权 求每个结点的子树中结点与根节点互质的个数

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
typedef long long  LL;
const int N = 100005;
vector <int> factor[N];
vector <int> edge[N];
void init(){     //预处理出(1~maxn)每个点的素因子并放入vector中
    for(int i=2;i<N;i++){
        factor[i].clear();
        int n = i;
        for(int j=2;j*j<=n;j++){
            if(n%j==0){
                factor[i].push_back(j);
                while(n%j==0) n/=j;
            }
        }
        if(n>1) factor[i].push_back(n);
    }
}
int cnt[N],val[N],ans[N];
int solve(int n,int val){    //求出与x不互斥的数的个数
    int len = factor[n].size(),ans=0;
    for(int i=1;i<(1<<len);i++){
        int odd = 0;
        int mul = 1;
        for(int j=0;j<len;j++){
            if((i>>j)&1){
                odd++;
                mul*=factor[n][j];
            }
        }
        if(odd&1){
            ans+=cnt[mul];
        }
        else ans-=cnt[mul];
        cnt[mul]+=val; 
    }
    return ans;
}
int dfs(int u,int pre){
    int L = solve(val[u],0);    //算出根以上与根不互素的节点数
    int s = 0; 
    for(int i=0;i<edge[u].size();i++){
        int v = edge[u][i];
        if(v==pre) continue;
        s+=dfs(v,u);
    }
    int R = solve(val[u],1);    //算出（根以下和根以上）与根不互素的节点数
    ans[u] = s - (R-L);     //s:子树的总结点 R-L是子树与跟不互质的个数 相减就是互质的个数 
    if(val[u]==1) ans[u]++;   //1和自己互素
    return s+1;              ////返回这棵子树的节点数包括根节点本身
}
int main()
{
    init();
    int n,t = 1;
    while(scanf("%d",&n)!=EOF){
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++) edge[i].clear();
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        for(int i=1;i<=n;i++) scanf("%d",&val[i]);
        dfs(1,-1);
        bool flag = true;
        printf("Case #%d: ",t++);
        for(int i=1;i<=n;i++){
            if(!flag) printf(" ");
            flag = false;
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

思路

这里root也算子树 所以return+1
子树用dfs序 其实就是在dfs序上求容斥 具体见注释

cf 620E

题目要求

一棵树 每个结点一种颜色 多次询问 每次询问两种操作
1.把结点v的子树结点颜色全部换成c
2.查询v的子树结点不同颜色的个数

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
#define maxn 400050
#define LL long long 
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int n,m,step;
int in[maxn],out[maxn];
LL c[maxn],id[maxn];
LL tree[maxn<<2],lazy[maxn<<2];
LL ans;
vector<int>e[maxn];
void init(){
	for(int i=0;i<=n;i++) e[i].clear();
	mm(in,0),mm(out,0),mm(c,0),mm(id,0);
	mm(tree,0),mm(lazy,0);
	step=1;
	ans=0;
}
void dfs(int x,int fa){
	in[x]=step,id[step]=x;
	int len=e[x].size();
	for(int i=0;i<len;i++){
		int next=e[x][i];
		if(next==fa) continue;
		step++;
		dfs(next,x);
	}
	out[x]=step;
}
void push_up(int rt){
	tree[rt]=tree[rt<<1]|tree[rt<<1|1];
}
void push_down(int rt){
	if(lazy[rt]){
		tree[rt<<1]=(1LL<<lazy[rt]);
		tree[rt<<1|1]=(1LL<<lazy[rt]);
		lazy[rt<<1]=lazy[rt];
		lazy[rt<<1|1]=lazy[rt];
		lazy[rt]=0;
	}
}
void build(int rt,int l,int r){
	if(l==r){
		tree[rt]=(1LL<<c[id[l]]);
		return;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	push_up(rt);
}
void update(int rt,int l,int r,int x,int L,int R){
	if(l>=L && r<=R){
		tree[rt]=(1LL<<x);
		lazy[rt]=x;
		return;
	}
	push_down(rt);
	int mid=(l+r)>>1;
	if(mid>=L) update(lson,x,L,R);
	if(mid<R) update(rson,x,L,R);
	push_up(rt);
}
void query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R){
		ans|=tree[rt];
		return;
	}
	push_down(rt);
	int mid=(l+r)>>1;
	if(mid>=L) query(lson,L,R);
	if(mid<R) query(rson,L,R);
}
int getsum(){
	int sum=0;
	while(ans){
		if(ans&1) sum++;
		ans>>=1;
	}
	return sum;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	init();
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	build(1,1,n);
	while(m--){
		int op;
		scanf("%d",&op);
		if(op==1){
			int x,y;
			scanf("%d%d",&x,&y);
			update(1,1,n,y,in[x],out[x]);
		}
		else{
			int x;
			scanf("%d",&x);
			query(1,1,n,in[x],out[x]);
			printf("%d\n",getsum());
		}
	}
	return 0;
}

思路

对子树的操作 转化成dfs序
由于颜色只有60种 所以使用集合来表示颜色 不会爆LL
线段树进行维护和查询颜色 最后ans里1的个数就是不同颜色的个数

cf 877E

题目要求

一棵树 每个结点有一个01初始值
给出若干个操作
get x表示查询x的子树中1的个数
pow x表示把x的子树0变1 1变0

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
#define maxn 200050
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int num0[maxn<<2],num1[maxn<<2],lazy[maxn<<2];
int in[maxn],out[maxn],val[maxn];
int a[maxn];
int n,q,step;
vector<int>e[maxn];
void init(){
	mm(in,0),mm(out,0);
	mm(num0,0),mm(num1,0);
	mm(val,0);
	for(int i=0;i<=n;i++) e[i].clear();
	step=0;
}
void dfs(int x,int fa){
	in[x]=++step;
	val[in[x]]=x;
	for(auto p:e[x]){
		if(p==fa) continue;
		dfs(p,x);
	}
	out[x]=step;
}
void push_up(int rt){
	num0[rt]=num0[rt<<1]+num0[rt<<1|1];
	num1[rt]=num1[rt<<1]+num1[rt<<1|1];
}
void push_down(int rt){
	if(lazy[rt]){
		lazy[rt<<1]^=1;
		lazy[rt<<1|1]^=1;
		swap(num0[rt<<1],num1[rt<<1]);
		swap(num0[rt<<1|1],num1[rt<<1|1]);
		lazy[rt]=0;
	}
}
void build(int rt,int l,int r){
	lazy[rt]=0;
	if(l==r){
		if(a[val[l]]==0) num0[rt]=1;
		if(a[val[l]]==1) num1[rt]=1;
		return;
	}
	int mid=l+r>>1;
	build(lson);
	build(rson);
	push_up(rt);
}
void update(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R){
		swap(num0[rt],num1[rt]);
		lazy[rt]^=1;
		return;
	}
	push_down(rt);
	int mid=l+r>>1;
	if(mid>=R) update(lson,L,R);
	else if(mid<L) update(rson,L,R);
	else update(lson,L,R),update(rson,L,R);
	push_up(rt);
}
int query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return num1[rt];
	push_down(rt);
	int mid=l+r>>1;
	if(mid>=R) return query(lson,L,R);
	else if(mid<L) return query(rson,L,R);
	else return query(lson,L,R)+query(rson,L,R);
}
char op[10];
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	init();
	for(int i=2;i<=n;i++){
		int x;
		scanf("%d",&x);
		e[x].push_back(i);
		e[i].push_back(x);
	}
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dfs(1,0);
	build(1,1,n);
	scanf("%d",&q);
	while(q--){
		scanf("%s",op);
		if(op[0]=='g'){
			int x;
			scanf("%d",&x);
			printf("%d\n",query(1,1,n,in[x],out[x]));
		}
		else{
			int x;
			scanf("%d",&x);
			update(1,1,n,in[x],out[x]);
		}
	}
	return 0;
}

思路

dfs序+线段树
线段树维护0的个数和1的个数以及异或的次数

本文标题:dfs序专题

文章作者:Hippopmonkey

发布时间:2017-08-18, 21:36:36

最后更新:2017-10-24, 18:37:43

原始链接:http://xuboming8.github.io/2017/08/18/dfs序专题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. dfs序专题
    1. 1.1. HDU 3887
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 5692
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. poj 3321(单点01修改+求子树的权值和)
    4. 1.4. fzu 2277(子树点权区间修改+单点查询)
    5. 1.5. HDU 5468
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. cf 620E
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. cf 877E
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
|