ACM_JLINE.

树链剖分专题

树链剖分
字数统计: 3.7k阅读时长: 21 min
2019/10/03 Share

树链剖分专题

国庆刷题，阅兵看了会，电影中国机长也还不错，买了第一排，表示只能捂着耳朵看。今天3号，马上小明敏要来上虞玩了，开心吖。然后再去个金华横店，美滋滋。

树上两条路径的交集

题目：

求树上两条路径相交点的个数

解题思路：

树链剖分裸题

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
const int N = 5e5 + 5;
int Size[N], fa[N], deep[N], son[N];
int top[N], dfn[N]; 
int cnt, a[N];
char ch[5];
int n, m, q;
vector <int> V[N];
 
void dfs1(int u, int pre){
	Size[u] = 1;
	fa[u] = pre;
	deep[u] = deep[pre] + 1;
	for(int i = 0; i < V[u].size(); i++){
		int v = V[u][i];
		if(v == pre) continue;
		dfs1(v, u);
		Size[u] += Size[v];
		if(Size[v] > Size[son[u]]){
			son[u] = v;
		}
	}
}
 
void dfs2(int u, int t){
	top[u] = t;
	dfn[u] = ++cnt;
	if(son[u]) dfs2(son[u], t);
	
	for(int i = 0; i < V[u].size(); i++){
		int v = V[u][i];
		if(v != son[u] && v != fa[u]){
			dfs2(v, v);
		}
	}
}
 
struct node{
    int l, r;
    ll sum, add;
}tree[N * 4];
 
void pushup(int x){
    tree[x].sum = tree[x * 2].sum + tree[x * 2 + 1].sum ;
}
 
void pushdown(int x){
    if(tree[x].add){
        tree[x * 2].sum += tree[x].add * (tree[x * 2].r - tree[x * 2].l + 1);
        tree[x * 2 + 1].sum += tree[x].add * (tree[x * 2 + 1].r - tree[x * 2 + 1].l + 1);
        tree[x * 2].add += tree[x].add;
        tree[x * 2 + 1].add += tree[x].add;
        tree[x].add = 0;
    }
}
 
void build(int x, int l, int r){
    tree[x].l = l, tree[x].r = r, tree[x].add = 0;
    if(l == r) {
        tree[x].sum = a[l]; 
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    pushup(x);
}
 
void add(int x, int l, int r, int c){
    if(l <= tree[x].l && r >= tree[x].r){
        tree[x].sum += c * (tree[x].r - tree[x].l + 1);
        tree[x].add += c;
        return;
    }
    pushdown(x);
    
    int mid = (tree[x].l + tree[x].r) / 2;
    if(l <= mid) add(x * 2, l, r, c);
    if(r > mid) add(x * 2 + 1, l, r, c);
    pushup(x);
}
 
ll ask(int x, int l, int r){
    if(l <= tree[x].l && r >= tree[x].r) return tree[x].sum;
    pushdown(x);
    int mid = (tree[x].l + tree[x].r) / 2;
    ll v = 0;
    if(l <= mid) v += ask(x * 2, l, r);
    if(r > mid) v += ask(x * 2 + 1, l, r);
    return v;
}
 
 
void change(int x, int y, int c){
	while(top[x] != top[y]){
		if(deep[top[x]] < deep[top[y]]){
			swap(x, y);
		}
		add(1, dfn[top[x]], dfn[x], c);
		x = fa[top[x]];
	
	}
	if(deep[x] > deep[y]) swap(x, y);
	add(1, dfn[x], dfn[y], c);
}
 
ll queryAns(int x, int y){
	ll ans = 0;
	while(top[x] != top[y]){
		if(deep[top[x]] < deep[top[y]]){
			swap(x, y);
		}
		ans += ask(1, dfn[top[x]], dfn[x]);
		x = fa[top[x]];
	}
		
	if(deep[x] > deep[y]) swap(x, y);
	ans += ask(1, dfn[x], dfn[y]);
	return ans;
}
 
 
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i < n; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		V[x].push_back(y), V[y].push_back(x);
	}
	
	dfs1(1, 0); dfs2(1, 1);
	build(1, 1, n);
	
	while(m--){
		int l, r, x, y;
		scanf("%d%d%d%d", &l, &r, &x, &y);
		change(l, r, 1);
		printf("%d\n", queryAns(x, y));
		change(l, r, -1);
	}
		
		
	return 0;
}

POJ 3237

题目：

一颗树边有权值

支持三种操作

  1. CHANGE i v 把第 i 条边的权值改成 v
  2. NEGATE a，b 把路劲 a 到 b 上的边权取反
  3. QUERY a，b 查询路劲 a 到 b 上的边权最大值

解题思路：

树链剖分（边权） 数段树维护最大 最小（因为有取反）一定要注意操作 1 时，pushdown！！！因为单点更新，就忽略了pushdown 被wa了好几发

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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 5e5 + 5;
const int INF = 0x3f3f3f3f;
int Size[N], fa[N], deep[N], son[N];
int top[N], dfn[N]; 
int cnt;
int n, m, q, t;
vector <int> V[N];
int num[N];
struct node
{
    int x, y;
    int z;
}a[N];
char ch[10];

void dfs1(int u, int pre){
    Size[u] = 1;
    fa[u] = pre;
    deep[u] = deep[pre] + 1;
    son[u] = 0;
    for(int i = 0; i < V[u].size(); i++){
        int v = V[u][i];
        if(v == pre) continue;
        dfs1(v, u);
        Size[u] += Size[v];
        if(Size[v] > Size[son[u]]){
            son[u] = v;
        }
    }
}

void dfs2(int u, int t){
    top[u] = t;
    dfn[u] = ++cnt;
    if(son[u]) dfs2(son[u], t);
    
    for(int i = 0; i < V[u].size(); i++){
        int v = V[u][i];
        if(v != son[u] && v != fa[u]){
            dfs2(v, v);
        }
    }
}

struct Tree{
    int l, r, add;
    int Max, Min;
}tree[N * 4];

void pushup(int x){
    tree[x].Max = max(tree[x * 2].Max, tree[x * 2 + 1].Max);
    tree[x].Min = min(tree[x * 2].Min, tree[x * 2 + 1].Min);
}

void solve(int &x, int &y){
    int t = x;
    x = -y;
    y = -t;
}


void pushdown(int x){
    if(tree[x].add){
        solve(tree[x * 2].Max, tree[x * 2].Min);
        solve(tree[x * 2 + 1].Max, tree[x * 2 + 1].Min);
        tree[x * 2].add  ^= 1;
        tree[x * 2 + 1].add ^= 1;
        tree[x].add = 0;
    }
}

void build(int x, int l, int r){
    tree[x].l = l, tree[x].r = r, tree[x].Max = -INF, tree[x].Min = INF, tree[x].add = 0;
    if(l == r) {
    	tree[x].Min = tree[x].Max = num[l];
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    pushup(x);
}

void add(int x, int l, int c){//把 l 上的值改成 c
    if(tree[x].l == tree[x].r){
        tree[x].Max = tree[x].Min = c;
        return;
    }
    pushdown(x);  //千万小心！！！
    int mid = (tree[x].l + tree[x].r) / 2;
    if(l <= mid) add(x * 2, l, c);
    else add(x * 2 + 1, l, c);
    pushup(x);
}

void add2(int x, int l, int r){//区间更新，操作2
    if( l <= tree[x].l && tree[x].r <= r){
        solve(tree[x].Max, tree[x].Min);
        tree[x].add ^= 1;
        return;
    }
    pushdown(x);
    int mid = (tree[x].l + tree[x].r) / 2;
    if(l <= mid) add2(x * 2, l, r);
    if(r > mid) add2(x * 2 + 1, l, r);
    pushup(x);
}

int queryMax(int x, int l, int r){ //求最大
    int res = -1e9;
    if(l <= tree[x].l && tree[x].r <= r){
        return tree[x].Max;
    }

    int mid = (tree[x].l + tree[x].r) / 2;
    pushdown(x);
    if(l <= mid) res = max(res, queryMax(2*x, l, r));
    if(r > mid) res = max(res, queryMax(2*x + 1, l, r));
    return res;
}



void change(int u, int c){ //操作1
    if(deep[a[u].x] > deep[a[u].y])
    add(1, dfn[a[u].x], c);
    else add(1, dfn[a[u].y], c);
}

void change2(int x, int y){ //操作2
    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]){
            swap(x, y);
        }
        add2(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
        
    if(deep[x] > deep[y]) swap(x, y);
    if(x != y){
        add2(1, dfn[x] + 1, dfn[y]);
    }
}

int queryAns(int x, int y){ //操作3
    int ans = -INF;
    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]){
            swap(x, y);
        }
        int tmp = queryMax(1, dfn[top[x]], dfn[x]);
           ans = max(ans, tmp);
        x = fa[top[x]];
    }
        
    if(deep[x] > deep[y]) swap(x, y);
    if(x != y){
        int tmp = queryMax(1, dfn[x] + 1, dfn[y]);
        ans = max(ans, tmp);
    }
    return ans;
}



int main(){

    scanf("%d", &t);
    while(t--){
        cnt = 0;
        for(int i = 0; i < N; i++) V[i].clear();
        
        scanf("%d", &n);
        for(int i = 1; i < n; i++){
            int x, y; int z;
            scanf("%d%d%d", &x, &y, &z);
            V[x].push_back(y), V[y].push_back(x);
            a[i].x = x, a[i].y = y, a[i].z = z;
        }
        dfs1(1, 0); dfs2(1, 1);
    
        for(int i = 1; i < n; i++){
            if(deep[a[i].x] > deep[a[i].y]){
                num[dfn[a[i].x]] = a[i].z;
            }
            else num[dfn[a[i].y]] = a[i].z;
        }
    
        build(1, 1, n);
        while(~scanf("%s", ch)){
            if(ch[0] == 'D') break;
            else if(ch[0] == 'C'){
                int x, y;
                scanf("%d%d", &x, &y);
                change(x, y);
            }
            else if(ch[0] == 'Q'){
                int x, y;
                scanf("%d%d", &x, &y);
                printf("%d\n", queryAns(x, y));
            }
            else {
                int x, y;
                scanf("%d%d", &x, &y);
                change2(x, y);
            }   
        }
    }    
        
    return 0;
}

求黑边cf165D

题目：

一颗树边默认都是黑色的 支持三种操作

  1. 把第 i 条边改成黑色（保证之前一定是白色的）
  2. 把第 i 条边改成白色（保证之前一定是黑色的）
  3. 求 a 到 b 的最短路劲有几条黑边，如果有白边输出 -1

解题思路：

树链剖分（边权） 数段树维护区间和 一开始都是1，操作 2 把边改成 -INF，操作 1 把边改成 INF 。

区间查询和小于 0 说明就有白边，输出 -1 即可。上代码。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 5e5 + 5;
const int INF = 0x3f3f3f3f;
int Size[N], fa[N], deep[N], son[N];
int top[N], dfn[N]; 
int cnt;
int n, m, q;
vector <int> V[N];
vector <pii> edge;
 
void dfs1(int u, int pre){
	Size[u] = 1;
	fa[u] = pre;
	deep[u] = deep[pre] + 1;
	for(int i = 0; i < V[u].size(); i++){
		int v = V[u][i];
		if(v == pre) continue;
		dfs1(v, u);
		Size[u] += Size[v];
		if(Size[v] > Size[son[u]]){
			son[u] = v;
		}
	}
}
 
void dfs2(int u, int t){
	top[u] = t;
	dfn[u] = ++cnt;
	if(son[u]) dfs2(son[u], t);
	
	for(int i = 0; i < V[u].size(); i++){
		int v = V[u][i];
		if(v != son[u] && v != fa[u]){
			dfs2(v, v);
		}
	}
}
 
struct node{
    int l, r;
    ll sum, add;
}tree[N * 4];
 
void pushup(int x){
    tree[x].sum = tree[x * 2].sum + tree[x * 2 + 1].sum ;
}
 
void pushdown(int x){
    if(tree[x].add){
        tree[x * 2].sum += tree[x].add * (tree[x * 2].r - tree[x * 2].l + 1);
        tree[x * 2 + 1].sum += tree[x].add * (tree[x * 2 + 1].r - tree[x * 2 + 1].l + 1);
        tree[x * 2].add += tree[x].add;
        tree[x * 2 + 1].add += tree[x].add;
        tree[x].add = 0;
    }
}
 
void build(int x, int l, int r){
    tree[x].l = l, tree[x].r = r, tree[x].add = 0;
    if(l == r) {
    	if(l == 1) tree[x].sum = 0;
        else tree[x].sum = 1; 
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    pushup(x);
}
 
void add(int x, int l, int r, int c){
    if(l <= tree[x].l && r >= tree[x].r){
        tree[x].sum += c * (tree[x].r - tree[x].l + 1);
        tree[x].add += c;
        return;
    }
    pushdown(x);
    
    int mid = (tree[x].l + tree[x].r) / 2;
    if(l <= mid) add(x * 2, l, r, c);
    if(r > mid) add(x * 2 + 1, l, r, c);
    pushup(x);
}
 
ll ask(int x, int l, int r){
    if(l <= tree[x].l && r >= tree[x].r) return tree[x].sum;
    pushdown(x);
    int mid = (tree[x].l + tree[x].r) / 2;
    ll v = 0;
    if(l <= mid) v += ask(x * 2, l, r);
    if(r > mid) v += ask(x * 2 + 1, l, r);
    return v;
}
 
 
void change(int x, int y, int c){
	while(top[x] != top[y]){
		if(deep[top[x]] < deep[top[y]]){
			swap(x, y);
		}
		add(1, dfn[top[x]], dfn[x], c);
		x = fa[top[x]];
	
	}
	if(deep[x] > deep[y]) swap(x, y);
	add(1, dfn[x], dfn[y], c);
}
 
ll queryAns(int x, int y){
	ll ans = 0;
	while(top[x] != top[y]){
		if(deep[top[x]] < deep[top[y]]){
			swap(x, y);
		}
		ans += ask(1, dfn[top[x]], dfn[x]);
		x = fa[top[x]];
	}
		
	if(deep[x] > deep[y]) swap(x, y);
	ans += ask(1, dfn[x], dfn[y]);
	ans -= ask(1, dfn[x], dfn[x]);
	return ans;
}
 
int f(int x){
	int u = edge[x - 1].first, v = edge[x - 1].second;
	if(u == fa[v]) return v;
	return u;
}
 
 
int main(){
	scanf("%d", &n);
	for(int i = 1; i < n; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		edge.push_back(pii(x, y));
		V[x].push_back(y), V[y].push_back(x);
	}
	dfs1(1, 0); dfs2(1, 1);
	build(1, 1, n);
	scanf("%d", &m);
	while(m--){
		int op, x, y;
		scanf("%d", &op);
		if(op == 3){
			scanf("%d%d", &x, &y);
			ll ans = queryAns(x, y);
			if(ans < 0){
				printf("-1\n");
			}
			else printf("%lld\n", ans);
		}
		else if(op == 2){
			int x;
			scanf("%d", &x);
			change(f(x), f(x), -INF);
		}
		else{
			int x;
			scanf("%d", &x);
			change(f(x), f(x), INF);
		}
	}
		
		
	return 0;
}

cf593

题目：

一颗树边默认都是黑色的 支持三种操作

  1. a，b，x，路径 a 到 b 上的边权为qi，求$\lfloor x/q1/q2/…/qi \rfloor$
  2. 把第 i 条边权改成 c

解题思路：

树链剖分（边权）

因为 $\lfloor x/q1/q2/…/qi \rfloor$ = $\lfloor x/（q1q2…*qi ）\rfloor$ 所以数段树维护区间乘积 注意区间乘积会爆ll，超过long long 处理成 INF。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 5e5 + 5;
const ll INF = 1e18;
int Size[N], fa[N], deep[N], son[N];
int top[N], dfn[N]; 
int cnt;
int n, m, q;
vector <int> V[N];
ll num[N];
struct node
{
    int x, y;
    ll z;
}a[N];
 
void dfs1(int u, int pre){
    Size[u] = 1;
    fa[u] = pre;
    deep[u] = deep[pre] + 1;
    for(int i = 0; i < V[u].size(); i++){
        int v = V[u][i];
        if(v == pre) continue;
        dfs1(v, u);
        Size[u] += Size[v];
        if(Size[v] > Size[son[u]]){
            son[u] = v;
        }
    }
}
 
void dfs2(int u, int t){
    top[u] = t;
    dfn[u] = ++cnt;
    if(son[u]) dfs2(son[u], t);
    
    for(int i = 0; i < V[u].size(); i++){
        int v = V[u][i];
        if(v != son[u] && v != fa[u]){
            dfs2(v, v);
        }
    }
}
 
struct Tree{
    int l, r;
    ll sum;
}tree[N * 4];
 
void pushup(int x){
    if(tree[x * 2].sum == 0) tree[x * 2].sum = 1;
    if(tree[x * 2 + 1].sum == 0) tree[x * 2 + 1].sum = 1;
    if(log(tree[x * 2].sum * 1.0) + log(tree[x * 2 + 1].sum * 1.0) > log(INF * 1.0))
        tree[x].sum = INF + 555 ;
    else tree[x].sum = tree[x * 2].sum * tree[x * 2 + 1].sum;
}
 
 
void build(int x, int l, int r){
    tree[x].l = l, tree[x].r = r;
    if(l == r) {
        tree[x].sum = num[l];
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    pushup(x);
}
 
void add(int x, int l, ll c){
    if(tree[x].l == tree[x].r){
        tree[x].sum = c;
        return;
    }
    
    int mid = (tree[x].l + tree[x].r) / 2;
    if(l <= mid) add(x * 2, l, c);
    else add(x * 2 + 1, l, c);
    pushup(x);
}
 
ll ask(int x, int l, int r){
    if(l <= tree[x].l && r >= tree[x].r) return tree[x].sum;
    int mid = (tree[x].l + tree[x].r) / 2;
    ll v = 1;
    if(l <= mid) {
    	ll tmp = ask(x * 2, l, r);
    	if(log(tmp * 1.0) + log(v * 1.0) > log(INF * 1.0))
    	v = INF + 555;
    	else v *= tmp;
	} 
    if(r > mid) {
    		ll tmp = ask(x * 2 + 1, l, r);
	    	if(log(tmp * 1.0) + log(v * 1.0) > log(INF * 1.0))
	    	v = INF + 555;
	    	else v *= tmp;
	}
    return v;
}
 
void change(int u, ll c){
    if(deep[a[u].x] > deep[a[u].y])
    add(1, dfn[a[u].x], c);
    else add(1, dfn[a[u].y], c);
}
 
ll queryAns(int x, int y){
    ll ans = 1;
    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]){
            swap(x, y);
        }
        ll tmp = ask(1, dfn[top[x]], dfn[x]);
        if(log(ans * 1.0) + log(tmp * 1.0) > log(INF * 1.0))
            ans = INF + 555;
        else ans *= tmp;
        x = fa[top[x]];
    }
        
    if(deep[x] > deep[y]) swap(x, y);
    if(x != y){
        ll tmp = ask(1, dfn[x] + 1, dfn[y]);
        if(log(ans * 1.0) + log(tmp * 1.0) > log(INF * 1.0))
            ans = INF + 555;
        else ans *= tmp;
    }
    return ans;
}
 
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i++){
        int x, y; ll z;
        scanf("%d%d%lld", &x, &y, &z);
        V[x].push_back(y), V[y].push_back(x);
        a[i].x = x, a[i].y = y, a[i].z = z;
    }
    dfs1(1, 0); dfs2(1, 1);
 
    for(int i = 1; i < n; i++){
        if(deep[a[i].x] > deep[a[i].y]){
            num[dfn[a[i].x]] = a[i].z;
        }
        else num[dfn[a[i].y]] = a[i].z;
    }
 
    build(1, 1, n);
    while(m--){
        int op, x, y; ll z;
        scanf("%d", &op);
        if(op == 1){
            scanf("%d%d%lld", &x, &y, &z);
            ll ans = queryAns(x, y);
            printf("%lld\n", z / ans);
        }
        else if(op == 2){
            scanf("%d%lld", &x, &z);
            change(x, z);
        }
    }     
    return 0;
}

原文作者：CHEN

原文链接：http://yourself.com/2019/10/03/树链剖分专题/

发表日期：October 3rd 2019, 10:58:10 pm

更新日期：October 3rd 2019, 10:58:10 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 树链剖分专题
    1. 1.1. 树上两条路径的交集
    2. 1.2. POJ 3237
    3. 1.3. 求黑边cf165D
    4. 1.4. cf593
Total : 28
2019
Invalid date
2019
Invalid date
Invalid date
2019
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
差分约束 KMP 二分 最短路 二分图 素数筛 LCA 树上差分 set维护 ICPC ccpc Hello CF 倍增 归并 随笔 贪心 map DP 树链剖分 树状数组 DFS CSP 贪心 并查集 dfs序 set 扫描线
ACM 最短路