树链剖分专题1

自用笔记算法

树链剖分专题1

专题1主要包括：

1.针对点权的树剖
2.针对边权的树剖
3.区间取反的特殊lazy

模版

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
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
void init(){
	for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    val[id[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
} 
int solvemx(int L,int R){
    int ans=-inf;
    while(top[L]!=top[R]){
        if(dep[top[L]]<dep[top[R]]) swap(L,R);
        ans=max(ans,querymx(1,id[top[L]],id[L]));
        L=fa[top[L]];
    }
    if(dep[L]>dep[R]) swap(L,R);
    ans=max(ans,querymx(1,id[L],id[R]));
    return ans;
}
int solvesum(int L,int R){
    int sum=0;
    while(top[L]!=top[R]){
        if(dep[top[L]]<dep[top[R]]) swap(L,R);
        sum+=querysum(1,id[top[L]],id[L]);
        L=fa[top[L]];
    }
    if(dep[L]>dep[R]) swap(L,R);
    sum+=querysum(1,id[L],id[R]);
    return sum;
}

HDU 6162

有最大值最小值限制的树链点权和
转跳链接

bzoj 1036

题目要求

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和
注意：从点u到点v的路径上的节点包括u和v本身

输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。
接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作的总数。
接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

参考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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<bits/stdc++.h>
#define maxn 30050
#define inf 0x3f3f3f3f
#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,q,step;
int w[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
struct T{
    int sum,Max,l,r;
}tree[maxn<<2];
vector<int>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0);
    mm(tree,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
void push_up(int rt){
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
    tree[rt].Max=max(tree[rt<<1].Max,tree[rt<<1|1].Max);
}
void build(int rt,int l,int r){
    tree[rt].l=l,tree[rt].r=r;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
}
void update(int rt,int u,int x){
    int l=tree[rt].l,r=tree[rt].r;
    int mid=(l+r)>>1;
    if(l==r){
        tree[rt].Max=tree[rt].sum=x;
        return;
    }
    if(mid>=u) update(rt<<1,u,x);
    else update(rt<<1|1,u,x);
    push_up(rt);
}
int querymx(int rt,int L,int R){
    int l=tree[rt].l,r=tree[rt].r;
    int mid=(l+r)>>1;
    if(l==L && r==R) return tree[rt].Max;
    else if(mid>=R) return querymx(rt<<1,L,R);
    else if(mid<L) return querymx(rt<<1|1,L,R);
    else return max(querymx(rt<<1,L,mid),querymx(rt<<1|1,mid+1,R));
}
int querysum(int rt,int L,int R){
    int l=tree[rt].l,r=tree[rt].r;
    int mid=(l+r)>>1;
    if(l==L && r==R) return tree[rt].sum;
    else if(mid>=R) return querysum(rt<<1,L,R);
    else if(mid<L) return querysum(rt<<1|1,L,R);
    else return querysum(rt<<1,L,mid)+querysum(rt<<1|1,mid+1,R);
}
int solvemx(int L,int R){
    int ans=-inf;
    while(top[L]!=top[R]){
        if(dep[top[L]]<dep[top[R]]) swap(L,R);
        ans=max(ans,querymx(1,id[top[L]],id[L]));
        L=fa[top[L]];
    }
    if(id[L]>id[R]) swap(L,R);
    ans=max(ans,querymx(1,id[L],id[R]));
    return ans;
}
int solvesum(int L,int R){
    int sum=0;
    while(top[L]!=top[R]){
        if(dep[top[L]]<dep[top[R]]) swap(L,R);
        sum+=querysum(1,id[top[L]],id[L]);
        L=fa[top[L]];
    }
    if(id[L]>id[R]) swap(L,R);
    sum+=querysum(1,id[L],id[R]);
    return sum;
}
int main(){
//  freopen("input.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        init();
        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);
        }
        for(int i=1;i<=n;i++) scanf("%d",&w[i]);
        dfs1(1,0,0);
        dfs2(1,1);
        build(1,1,n);
        for(int i=1;i<=n;i++) update(1,id[i],w[i]);
        scanf("%d",&q);
        while(q--){
            char op[10];
            int x,y;
            scanf("%s%d%d",op,&x,&y);
            if(op[0]=='C'){
                w[x]=y;
                update(1,id[x],y);
            }
            else{
                if(op[1]=='M') printf("%d\n",solvemx(x,y));
                else printf("%d\n",solvesum(x,y));
            }
        }
    }
    return 0;
}

思路

树剖模版题
单点更新+区间查询树链sum+区间查询树链max

HDU 3966

题目要求

树链上区间更新 单点查询
与上一题相反

参考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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
#define maxn 50050
#define inf 0x3f3f3f3f
#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,q,step;
int w[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
int val[maxn];
struct T{
    int sum,Max,lazy;
}tree[maxn<<2];
vector<int>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0),mm(val,0);
    mm(tree,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    val[id[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
void push_up(int rt){
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void push_down(int rt){
	if(tree[rt].lazy){
		tree[rt<<1].lazy+=tree[rt].lazy;
		tree[rt<<1|1].lazy+=tree[rt].lazy;
		tree[rt<<1].sum+=tree[rt].lazy;
		tree[rt<<1|1].sum+=tree[rt].lazy;
		tree[rt].lazy=0;
	}
}
void build(int rt,int l,int r){
    if(l==r){
    	tree[rt].sum=w[val[l]];
    	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,int x){
    if(l>=L && r<=R){
        tree[rt].sum+=x;
        tree[rt].lazy+=x;
        return;
    }
    int mid=(l+r)>>1;
    push_down(rt);
	if(mid>=L) update(lson,L,R,x);
	if(mid<R) update(rson,L,R,x);
    push_up(rt);
}
int query(int rt,int l,int r,int val){
    if(l==r) return tree[rt].sum;
    int mid=(l+r)>>1;
    push_down(rt);
    int ans=0;
	if(mid>=val) ans=query(lson,val);
    else ans=query(rson,val);
    return ans;
}
void change(int x,int y,int val){
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);  
        update(1,1,n,id[top[x]],id[x],val);  
        x=fa[top[x]];  
    }  
    if(dep[x]>dep[y]) swap(x,y);  
    update(1,1,n,id[x],id[y],val);  
}
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d%d%d",&n,&m,&q)!=EOF){
        init();
        for(int i=1;i<=n;i++) scanf("%d",&w[i]);
		for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs1(1,0,0);
        dfs2(1,1);
        build(1,1,n);
        while(q--){
            char op;
            cin>>op;
            if(op=='I'){
            	int c1,c2,k;
            	scanf("%d%d%d",&c1,&c2,&k);
            	change(c1,c2,k);
			}
			else if(op=='D'){
				int c1,c2,k;
            	scanf("%d%d%d",&c1,&c2,&k);
            	change(c1,c2,-k);
			}
			else{
				int x;
				scanf("%d",&x);
				printf("%d\n",query(1,1,n,id[x]));
			}
        }
    }
    return 0;
}

思路

只有区间操作要用到树剖的合并 所以本题的更新改为change操作
而单点查询用普通的线段树即可

SPOj QTREE

题目要求

一棵树 给出边权
单点更新区间查询

参考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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
#define maxn 20050
#define inf 0x3f3f3f3f
#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,step;
int w[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
int val[maxn];
int fi[maxn],se[maxn]; 
struct node{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
int Max[maxn<<2];
vector<node>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0),mm(val,0);
    mm(Max,0),mm(fi,0),mm(se,0),mm(w,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to;
        if(next==f) continue;
        w[next]=e[x][i].w;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    val[id[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to;
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
void push_up(int rt){
    Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}
void build(int rt,int l,int r){
    if(l==r){
    	Max[rt]=w[val[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 k){
    if(l==r){
    	Max[rt]=k;
    	return;
	}
	int mid=(l+r)>>1;
	if(mid>=x) update(lson,x,k);
	else update(rson,x,k);
	push_up(rt);
}
int query(int rt,int l,int r,int L,int R){
    if(l>=L && r<=R) return Max[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 max(query(lson,L,R),query(rson,L,R));
}
int querymx(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans=max(ans,query(1,1,n,id[top[x]],id[x]));
        x=fa[top[x]];  
    } 
    if(x==y) return ans;
    if(dep[x]>dep[y]) swap(x,y);
    ans=max(ans,query(1,1,n,id[son[x]],id[y]));
	return ans;
}
char op[10];
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		init();
		for(int i=1;i<n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			fi[i]=u,se[i]=v;
			e[u].push_back(node(v,w));
			e[v].push_back(node(u,w));
		}
		dfs1(1,0,1);
		dfs2(1,1); 
		build(1,1,n);
		for(int i=1;i<n;i++) fi[i]=dep[fi[i]]>dep[se[i]]?fi[i]:se[i]; 
		while(scanf("%s",op)!=EOF){
			if(op[0]=='D') break;
			if(op[0]=='Q'){
				int x,y;
				scanf("%d%d",&x,&y);
				printf("%d\n",querymx(x,y)); 
			}
			else{
				int x,y;
				scanf("%d%d",&x,&y);
				update(1,1,n,id[fi[x]],y);
			}
		}
	}
    return 0;
}

思路

由于是基于边权而不是点权 要做如下修改：
1.记录下点 fi和se数组
2.querymx里查询的是son[x]
3.需要让fi和se有序
4.注意dfs1里w数组的更新

poj 2763

题目要求

跟上题类似
针对边权的树 单点更新 区间查询
区别在于这里的起点不是1 而是s 并随着移动而改变

参考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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <cstdio>  
#include <cstring>  
#include <vector>  
#include <algorithm>
#define maxn 100500
#define inf 0x3f3f3f3f
#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,q,s,step;
int w[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
int val[maxn];
int fi[maxn],se[maxn]; 
struct node{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
int sum[maxn<<2];
vector<node>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0),mm(val,0);
    mm(sum,0),mm(fi,0),mm(se,0),mm(w,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to;
        if(next==f) continue;
        w[next]=e[x][i].w;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    val[id[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to;
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r){
    if(l==r){
    	sum[rt]=w[val[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 k){
	if(l==r){
		sum[rt]=k;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=x) update(lson,x,k);
	else update(rson,x,k);
	push_up(rt);
}
int query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return sum[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);
}
int querysum(int x,int y){
	int Sum=0;
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
		Sum+=query(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];  
    } 
    if(x==y) return Sum;
    if(dep[x]>dep[y]) swap(x,y);
    Sum+=query(1,1,n,id[son[x]],id[y]);
	return Sum;
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d%d",&n,&q,&s)!=EOF){
		init();
		for(int i=1;i<n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			fi[i]=u,se[i]=v;
			e[u].push_back(node(v,w));
			e[v].push_back(node(u,w));
		}
		dfs1(1,0,1);
		dfs2(1,1); 
		build(1,1,n);
		for(int i=1;i<n;i++) fi[i]=dep[fi[i]]>dep[se[i]]?fi[i]:se[i]; 
		while(q--){
			int op;
			scanf("%d",&op);
			if(op==0){
				int x;
				scanf("%d",&x);
				printf("%d\n",querysum(s,x));
				s=x;
			}
			else{
				int x,y;
				scanf("%d%d",&x,&y);
				update(1,1,n,id[fi[x]],y);
			}
		}
	}
    return 0;
}

思路

跟上题类似
用线段树维护sum 并注意s要实时更新

fzu 2082

题目要求

基于边权的树
单点更新 区间查询 与上题类似

参考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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <cstdio>  
#include <cstring>  
#include <vector>
#include<iostream>
#include <algorithm>
#define maxn 100500
#define inf 0x3f3f3f3f
#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,q,step;
int w[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
int val[maxn];
int fi[maxn],se[maxn]; 
struct node{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
int sum[maxn<<2];
vector<node>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0),mm(val,0);
    mm(sum,0),mm(fi,0),mm(se,0),mm(w,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to;
        if(next==f) continue;
        w[next]=e[x][i].w;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    val[id[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to;
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r){
    if(l==r){
    	sum[rt]=w[val[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 k){
	if(l==r){
		sum[rt]=k;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=x) update(lson,x,k);
	else update(rson,x,k);
	push_up(rt);
}
int query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return sum[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);
}
int querysum(int x,int y){
	int Sum=0;
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
		Sum+=query(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];  
    } 
    if(x==y) return Sum;
    if(dep[x]>dep[y]) swap(x,y);
    Sum+=query(1,1,n,id[son[x]],id[y]);
	return Sum;
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&q)!=EOF){
		init();
		for(int i=1;i<n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			fi[i]=u,se[i]=v;
			e[u].push_back(node(v,w));
			e[v].push_back(node(u,w));
		}
		dfs1(1,0,1);
		dfs2(1,1); 
		build(1,1,n);
		for(int i=1;i<n;i++) fi[i]=dep[fi[i]]>dep[se[i]]?fi[i]:se[i]; 
		while(q--){
			int op;
			scanf("%d",&op);
			if(op==0){
				int x,y;
				scanf("%d%d",&x,&y);
				update(1,1,n,id[fi[x]],y);
			}
			else{
				int x,y;
				scanf("%d%d",&x,&y);
				printf("%d\n",querysum(x,y));
			}
		}
	}
    return 0;
}

思路

模版题
注意基于边权的树链剖分

poj 3237

题目要求

基于边权的树
单点更新 区间取反
最后区间询问最大值

参考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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<bits/stdc++.h>
#define maxn 20050
#define inf 0x3f3f3f3f
#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,step;
int w[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
int val[maxn];
int fi[maxn],se[maxn]; 
struct node{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
int Max[maxn<<2],Min[maxn<<2],lazy[maxn<<2];
vector<node>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0),mm(val,0),mm(lazy,0);
    mm(Max,0),mm(Min,0),mm(fi,0),mm(se,0),mm(w,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to;
        if(next==f) continue;
        w[next]=e[x][i].w;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    val[id[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to;
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
void push_up(int rt){
    Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
    Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);
}
void push_down(int rt){
	if(lazy[rt]){
		lazy[rt<<1]^=1;
		lazy[rt<<1|1]^=1;
		swap(Max[rt<<1],Min[rt<<1]);
		Max[rt<<1]=-Max[rt<<1];
		Min[rt<<1]=-Min[rt<<1];
		swap(Max[rt<<1|1],Min[rt<<1|1]);
		Max[rt<<1|1]=-Max[rt<<1|1];
		Min[rt<<1|1]=-Min[rt<<1|1];
		lazy[rt]=0;
	}
}
void build(int rt,int l,int r){
    if(l==r){
    	Max[rt]=Min[rt]=w[val[l]];
    	return;
	}
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
void change(int rt,int l,int r,int x,int k){
	if(l==r){
		Max[rt]=Min[rt]=k;
		return;
	}
	push_down(rt);
	int mid=(l+r)>>1;
	if(mid>=x) change(lson,x,k);
	else change(rson,x,k);
	push_up(rt);
}
void negat(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R){
		swap(Max[rt],Min[rt]);
		Max[rt]=-Max[rt];
		Min[rt]=-Min[rt];
		lazy[rt]^=1;
		return;
	}
	push_down(rt);
	int mid=(l+r)>>1;
	if(mid>=R) negat(lson,L,R);
	else if(mid<L) negat(rson,L,R);
	else{
		negat(lson,L,R);
		negat(rson,L,R);
	}
	push_up(rt);
}
int query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return Max[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 max(query(lson,L,R),query(rson,L,R));
}
int querymx(int x,int y){
	if(x==y) return 0;
	int ans=-inf;
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans=max(ans,query(1,1,n,id[top[x]],id[x]));
        x=fa[top[x]];  
    } 
    if(x==y) return ans;
    if(dep[x]>dep[y]) swap(x,y);
    ans=max(ans,query(1,1,n,id[son[x]],id[y]));
	return ans;
}
void solvene(int x,int y){
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
		negat(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];  
    } 
    if(x==y) return ;
    if(dep[x]>dep[y]) swap(x,y);
    negat(1,1,n,id[son[x]],id[y]);
}
char op[10];
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		init();
		for(int i=1;i<n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			fi[i]=u,se[i]=v;
			e[u].push_back(node(v,w));
			e[v].push_back(node(u,w));
		}
		dfs1(1,0,1);
		dfs2(1,1); 
		build(1,1,n);
		for(int i=1;i<n;i++) fi[i]=dep[fi[i]]>dep[se[i]]?fi[i]:se[i]; 
		while(scanf("%s",op)!=EOF){
			if(op[0]=='D') break;
			if(op[0]=='C'){
				int x,y;
				scanf("%d%d",&x,&y);
				change(1,1,n,id[fi[x]],y);
			}
			else if(op[0]=='N'){
				int x,y;
				scanf("%d%d",&x,&y);
				solvene(x,y);
			}
			else {
				int x,y;
				scanf("%d%d",&x,&y);
				printf("%d\n",querymx(x,y));
			}
		}
	}
    return 0;
}

思路

区间取反的操作：线段树维护最小值和最大值 只需把最大值最小值交换取反即可满足取反的操作
lazy维护取反操作的次数 使用异或可以满足偶数次取反等于不变的性质
注意：本题由于取反存在负数的情况 所以querymx里的ans必须初始化为-inf 相对应也要加一句if x==y return 0

本文标题:树链剖分专题1

文章作者:Hippopmonkey

发布时间:2017-08-23, 10:15:33

最后更新:2017-09-18, 20:32:03

原始链接:http://xuboming8.github.io/2017/08/23/树链剖分专题/

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

文章目录
  1. 1. 树链剖分专题1
    1. 1.1. 模版
    2. 1.2. HDU 6162
    3. 1.3. bzoj 1036
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 3966
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. SPOj QTREE
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. poj 2763
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. fzu 2082
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
    8. 1.8. poj 3237
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
|