树的dfs序入门,BZOJ1103 ,hdu6162,EOJ3335

Posted by Cww97 on 2017-08-23

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/77509373
讨论昨天的02

克拉丽丝说不需要树剖可以直接dfs序

我不理解

他就丢给我这题,曰:经典的题目

百度题解一堆,好算知道dfs序是啥意思了

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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5 + 7;
int l[N], r[N];

struct binaryIndexTree{
int tree[N], n;
inline void init(int n){
this->n = n;
memset(tree, 0, sizeof(tree));
}
inline void add(int k, int num){
for (;k <= n; k += k&-k) tree[k] += num;
}
int sum(int k){
int sum = 0;
for (; k; k -= k&-k) sum += tree[k];
return sum;
}
} T;

struct graph{
struct Edge{
int from, to, nxt;
Edge(){}
Edge(int u, int v, int n):from(u), to(v), nxt(n){}
}edges[N];
int n, E, head[N];
int top;

inline void AddEdge(int f, int t){
edges[++E] = Edge(f, t, head[f]);
head[f] = E;
}
inline void Init(int n){
this -> n = n ; E = -1; top = 0;
for (int i = 0; i <= n; i++) head[i] = -1;
}
void dfs(int u){
l[u] = ++top; T.add(top, 1);
for (int i = head[u]; i != -1; i = edges[i].nxt){
dfs(edges[i].to);
}
r[u] = ++top; T.add(top, -1);
}
} g ;

int main(){
//freopen("in.txt", "r", stdin);
int n, m, u, v;
char ch;
for (; ~scanf("%d", &n);){
g.Init(n);
T.init(n*2);
for (int i = 1; i < n; i++){
scanf("%d%d", &u, &v);
if (u > v) swap(u, v);
g.AddEdge(u, v);
}
g.dfs(1);

scanf("%d", &m);
for (m += n-1; m--;){
getchar();
scanf("%c %d", &ch, &u);
if (ch == 'W') printf("%d\n", T.sum(l[u])-1);
else {
scanf("%d", &v);
if (u > v) swap(u, v);
T.add(l[v], -1); T.add(r[v], 1);
}
}
}
return 0;
}

写完之后,换了种实现昨天02的方法

dfs序配合之前写的离线查询

树状数组更加舒服

这里测试了一下效率

这里写图片描述
这里写图片描述

一开始在hdu似乎wa和MLE,后来发现fa[N][22]太大了,改成fa[N][18],

fa需要memset,一开始没有memset报WA,后来memset报MLE

改小了,memset才能Accept,也就是说,hdu的评测机,如果没有用到开到的内存,是不会爆MLE的

wa的原因是

1
2
3
for (int i = LCADEP; i >= 0; i--) if (fa[x][i] != fa[y][i]){
x = fa[x][i]; y = fa[y][i];
}

如果前一组数据比后一组大,不memset fa的话,会因为前一组的傻逼值而算错lca

还有

本题原来北邮提供的数据是个巨型菊花图,章鱼哥嫌弃数据太弱了

加强了一波数据放在了EOJ3335上,各位非暴力选手可以试试了

非常艰难的在hdu上用树状数组过了之后,作死想用线段树,然后wa哭了

然而又一次轻松的在EOJ上过了,章鱼哥说EOJ是单组数据评测

这里写图片描述
这里写图片描述

ZKW线段树固然常数小,不过还是比树状数组差一点,很接近

下面这段代码,hdu会蜜汁wa,我已经不想管了,想在hdu上A掉,把线段树删了,树状数组保留就好,注释都有,模快化很容易改

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
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
typedef long long LL;
int l[N], r[N];

struct gift{
int pos;
LL val;
void read(int id){
scanf("%lld", &val);
pos = id;
}
bool operator < (const gift & b) const {
return val < b.val;
}
} gifts[N];

int ks[N * 2], K, H;
map<LL, int> hashK;
vector<int> whoAsk[N*2];
void insertK(int id, LL k){
if (hashK.find(k) == hashK.end()) {
hashK[k] = ++H;
whoAsk[H].clear();
}
whoAsk[hashK[k]].push_back(id);
}
struct ask{
int u, v, pos;
LL a, b;
vector<LL> ans;

void read(int pos){
this->pos = pos;
ans.clear();
scanf("%d%d%lld%lld", &u, &v, &a, &b);
a--;
ks[++K] = a, ks[++K] = b;
insertK(pos, a);
insertK(pos, b);
}
inline void print(){
printf("%lld", abs(ans[1] - ans[0]));
}
} asks[N];

struct binaryIndexTree{
LL val[N * 2];
int n;
inline void build(int n){
this->n = n;
memset(val, 0, sizeof(val));
}
inline void add(int k, LL num){
for (;k <= n; k += k&-k) val[k] += num;
}
LL sum(int k){
if (k == 0) return 0;
LL sum = 0;
for (; k; k -= k&-k) sum += val[k];
return sum;
}
} TT ;

struct segTree{
LL tree[N * 6];
int M;
inline void build(int n){
M = 1; for(;M<n;) M<<=1; if(M!=1)M--;
memset(tree, sizeof(tree), 0);
}
void add(int t, LL x){
for (tree[t+=M]+=x, t>>=1; t; t>>=1){
tree[t] = tree[t<<1] + tree[t<<1^1];
}
}
LL sum(int l, int r){
if (l > r || r == 0) return 0;
LL ans = 0;
for (l+=M-1,r+=M+1; l^r^1; l>>=1,r>>=1){
if (~l&1) ans += tree[l^1];
if ( r&1) ans += tree[r^1];
}
return ans;
}
} T;

struct graph{
struct Edge{
int from, to, nxt;
Edge(){}
Edge(int u, int v, int n):from(u), to(v), nxt(n){}
} edges[N * 2];
static const int LCADEP = 17;
int n, E, head[N];
int top, dep[N], fa[N][LCADEP + 1];

inline void AddEdge(int f, int t){
edges[++E] = Edge(f, t, head[f]);
head[f] = E;
}
inline void Init(int n){
this -> n = n ; E = -1; top = 0; dep[0] = 0;
for (int i = 0; i <= n; i++) head[i] = -1;
memset(fa, 0, sizeof(fa));
}

void dfs(int u, int pre){
l[u] = ++top;
//printf("l[%d] = %d\n", u, top);
fa[u][0] = pre;
dep[u] = dep[pre] + 1;
for (int i = 1; i <= LCADEP; i++){
if (dep[u] < (1<<i)) break;
fa[u][i] = fa[fa[u][i-1]][i-1];
}
for (int i = head[u]; i != -1; i = edges[i].nxt){
if (edges[i].to != pre) dfs(edges[i].to, u);
}
r[u] = ++top;
//printf("r[%d] = %d\n", u, top);
}

int lca(int x, int y){
if (dep[x] < dep[y]) swap(x,y);
int t = dep[x] - dep[y];
for (int i = 0; i <= LCADEP; i++) if ((1<<i) & t) x = fa[x][i];
for (int i = LCADEP; i >= 0; i--) if (fa[x][i] != fa[y][i]){
x = fa[x][i]; y = fa[y][i];
}
return x==y ? x : fa[x][0];
}

void solve(ask &a){
int u = a.u, v = a.v;
int f = lca(u, v);
LL ans = T.sum(1, l[u]) + T.sum(1, l[v]) - T.sum(1, l[f]) - T.sum(1, l[fa[f][0]]);
//LL ans = T.sum(l[u]) + T.sum(l[v]) - T.sum(l[f]) - T.sum(l[fa[f][0]]);
a.ans.push_back(ans);
}
} g ;

int main () {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int n, m, u, v;
for (; cin >> n >> m;) {
for(int i = 1; i <= n; i++) gifts[i].read(i);
sort(gifts + 1, gifts + n+1);
g.Init(n);
for(int i = 0; i < n - 1; i++) {
scanf("%d%d", &u, &v);
g.AddEdge(u, v);
g.AddEdge(v, u);
}
g.dfs(1, 0);

T.build(n*2);
K = 0, H = 0;
hashK.clear();
for (int i = 1; i <= m; i++) asks[i].read(i);
sort(ks + 1, ks + K+1);
K = unique(ks + 1, ks + K+1) - (ks + 1);

int cur = 1;
for (int i = 1; i <= K; i++){
//printf("ks[%d] = %d\n", i, ks[i]);
for (int &j = cur; j <= n; j++){
if (gifts[j].val > ks[i]) break;
//printf("gifts[%d].val = %d, pos = %d, [%d, %d]\n", j, gifts[j].val, gifts[j].pos, l[gifts[j].pos], r[gifts[j].pos]);
T.add(l[gifts[j].pos], gifts[j].val);
T.add(r[gifts[j].pos],-gifts[j].val);
}
int kk = hashK[ks[i]];
for (int j = 0; j < whoAsk[kk].size(); j++){
ask &a = asks[whoAsk[kk][j]];
g.solve(a);
}
}

for (int i = 1; i <= m; i++){
asks[i].print();
putchar(i==m ? '\n' : ' ');
}
}
return 0;
}