POJ 2763 Housewife Wind (LCA,RMQ,BIT)

题目链接:
POJ 2763 Housewife Wind (LCA,RMQ,BIT)

题意分析:
给出两个操作,0:妈妈需要到树上某个结点接孩子,每次输出最短距离,然后妈妈的位置变成孩子所在的位置。1:更改树上某条边的距离为w。


解题思路:
由于每次移动都会使得母亲的位置变动,这里我们需要使用LCA的在线算法。
首先,我们将整棵树根据后序遍历拉成一条链,每次记录这个链上结点代表的结点是什么(vs[i])和深度是多少(dep[i]),顺便记录这个结点第一次出现的时候是在链上什么位置(id[i])。然后每次$lca(a,b)$其实就是查询$[id[a],id[b]]$这个区间内,dep最小的那个下标是什么。
其次,由于本题涉及到更新操作,如上我们已经把它拉成一条链了,所以下一步只需在父亲指向儿子的边加权值,儿子指向父亲的边减权值,然后查询区间$$sum(id[a])+sum(id[b])-2 \times sum(id[lca(a,b)])$$即可。

个人感受:
爽呆了这题,为了A这题,A了两道RMQ,复习了BIT,爽23333

具体代码如下:
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<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
using namespace std;
const int MAXN = 1e5 + 111;
struct Edge {
int to, id, w, next;
}edge[MAXN * 2];
int head[MAXN], tol;
void addedge(int u, int v, int id, int w) {
edge[tol].to = v; edge[tol].w = w; edge[tol].id = id;
edge[tol].next = head[u]; head[u] = tol++;
}
int s, bitn;
int w[MAXN];
vector<Edge> G[MAXN];
int id[MAXN], es[MAXN * 2], dep[MAXN * 2], vs[MAXN * 2];
int bit[MAXN * 2], dp[MAXN * 2][20];
void add(int i, int x) {
while (i <= bitn) {
bit[i] += x;
i += lowbit(i);
}
}
int sum(int i) {
int ret = 0;
while (i > 0) {
ret += bit[i];
i -= lowbit(i);
}
return ret;
}
void dfs(int u, int p, int sum, int &k) {
id[u] = k;
vs[k] = u;
dep[k++] = sum;
for (int i = head[u]; ~i; i = edge[i].next) {
Edge &e = edge[i];
if (e.to != p) {
add(k, e.w);
es[e.id * 2] = k;
dfs(e.to, u, sum + e.w, k);
vs[k] = u;
dep[k++] = sum;
add(k, -e.w);
es[e.id * 2 + 1] = k;
}
}
}
int my_min(int a, int b) {
return dep[a] <= dep[b] ? a : b;
}
void init_rmq(int n) {
for (int i = 0; i <= n; ++i) dp[i][0] = i;
for (int j = 1; j < 20; ++j) {
for (int i = 0; i + (1 << j) - 1 <= n; ++i) {
dp[i][j] = my_min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
}
void init(int n) {
bitn = n * 2 - 1;
memset(bit, 0, sizeof bit);
int k = 0;
dfs(0, -1, 0, k);
init_rmq(2 * n - 1);
}
int query(int l, int r) {
int k = log2(r - l + 1);
return my_min(dp[l][k], dp[r - (1 << k) + 1][k]);
}
int lca(int a, int b) {
if (id[a] > id[b]) swap(a, b);
return vs[query(id[a], id[b])];
}
int main()
{
int n, q, u, v;
while (~scanf("%d%d%d", &n, &q, &s)) {
for (int i = 0; i < n; ++i) G[i].clear(), head[i] = -1;
tol = 0;
for (int i = 0; i < n - 1; ++i) {
scanf("%d%d%d", &u, &v, &w[i]);
--u, --v;
addedge(u, v, i, w[i]);
addedge(v, u, i, w[i]);
}
init(n);
int op, a, b;
--s;
for (int i = 0; i < q; ++i) {
scanf("%d%d", &op, &a);
--a;
if (op == 0) {
int p = lca(s, a);
printf("%d\n", sum(id[s]) + sum(id[a]) - 2 * sum(id[p]));
s = a;
}
else {
scanf("%d", &b);
add(es[2 * a], b - w[a]);
add(es[2 * a + 1], w[a] - b);
w[a] = b;
}
}
}
return 0;
}

广告时间

Java学习网站: how2j

VPS: VPS

梦想世界上每个人都能给我一元钱,2333