poj2763(dfs序+BIT+LCA)

挑战程序设计里面的一道题目,然而调整很长的时间,结果T了emmmm
其中的思想还是相当的重要的

题目

poj2763

题意

给定一张树形图,n个节点,n-1条边。
有两个种类的询问:

  1. 从这个点到目标点路径的权值
  2. 改变某条边的权值

题解

  1. 针对第一种操作,我们先预处理出来LCA, 然后求出每个点到root点的路径权重和(为什么算出来的是一条路径的呢?因为回边会相互抵消。)。
    1
    sum(id[v])+sum(id[u])-2*sum(id[p])

  1. 对第二种操作,只要改变相应的边权,然后在BIT中进行相应的更新就可以了

dfs序的说明:
vs[k] = v: 表示的是dfs第k次访问的时候,到达的顶点是v
depth[k] = d: 表示的是dfs第k次访问的时候, 所在节点的深度为d
id[v]=k: 表示节点v第一次被访问的时候访问的编号,这个非常的有用
假设我们在id[u]~id[v]之间, dfs访问了很多个节点,这样就能形成了一个链,将树形的结构转变为线性的结构。

T了的代码

期间遇到了:

  • 数组开的太小RE了
  • 开的ll, 输出为d的表达错误,一度怀疑人生。
  • 好不容易调好了,结果T了。
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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxv = 1e5+10;
typedef long long ll;
int a[maxv], b[maxv], weight[maxv];
int n, q, s;
int type[maxv];
//max_q == max_v
int x[maxv], t[maxv];
int root;
int vs[maxv*2];
int depth[maxv*2];
int id[maxv];
int es[maxv*2];
struct Edge{
int id, to, cost;
};
vector<Edge> G[maxv];
//c数组怎么初始化.在dfs的时候初始化了。
ll c[maxv*2];
void add(int i, int val){
while(i<=maxv*2){
c[i] += val;
i += i&(-i);
}
}
int sum(int i){
ll ans = 0;
while(i>0){
ans += c[i];
i -= i&(-i);
}
return ans;
}
void dfs(int v, int p, int d, int& k){
// printf("depth: %d\n", d);
// printf("%d %d\n", v, k);
id[v] = k;
vs[k] = v;
depth[k++] = d;
for(int i=0; i<G[v].size(); i++){
Edge &e = G[v][i];
if(e.to!=p){
add(k, e.cost);
es[e.id*2] = k;
dfs(e.to, v, d+1, k);
vs[k] = v;
depth[k++] = d;
add(k, -e.cost);
es[e.id*2+1] = k;
}
}
}
int d[maxv*2][21];
int min_index(int i, int j){
return depth[i]<depth[j]?i:j;
}
void rmq_init(int n){
for(int i=0; i<n; i++){
d[i][0] = i;
}
for(int j=1; (1<<j)<=n; j++){
for(int i=0; (i+(1<<j))<n; i++){
d[i][j] = min_index(d[i][j-1], d[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l ,int r){
int k = floor(log2(r-l+1));
//printf("value: %d\n", k);
return min_index(d[l][k], d[r-(1<<k)+1][k]);
}
int lca(int u, int v){
int l = min(id[u], id[v]);
int r = max(id[u], id[v]);
// printf("lr:%d %d\n", l, r);
int val = query(l, r);
//printf("val: %d\n", val);
return vs[val];
//return -1;
}
void init(int n){
int d = 0, k =0;
dfs(root, -1, d, k);
rmq_init(n*2-1);
}
void solve(){
root = n/2;
for(int i=0; i<n-1; i++){
G[i].clear();
}
for(int i=0; i<n-1; i++){
G[a[i]-1].push_back(Edge{i, b[i]-1, weight[i]});
G[b[i]-1].push_back(Edge{i, a[i]-1, weight[i]});
}
init(n);
int v = s-1;
for(int i=0; i<q; i++){
if(type[i] == 0){
int u = x[i]-1;
int p = lca(v, u);
//printf("the lca is:%d %d--%d\n", p, u, v);
//printf("%d %d %d\n",sum(id[u]), sum(id[v]), sum(id[p]) );
printf("%d\n", sum(id[v])+sum(id[u])-2*sum(id[p]));
v = u;
}
else{
int k = x[i]-1;
add(es[k*2], t[i]-weight[k]);
add(es[k*2+1], weight[k]-t[i]);
weight[k] = t[i];
}
}
}
int main()
{
while(~scanf("%d%d%d", &n, &q, &s)){
for(int i=0; i<n-1; i++){
scanf("%d%d%d", &a[i], &b[i], &weight[i]);
}
memset(c, 0, sizeof(c));
for(int i=0; i<q; i++){
scanf("%d", &type[i]);
if(type[i] == 0){
scanf("%d", &x[i]);
}
else{
scanf("%d%d", &x[i], &t[i]);
}
}
solve();
}
return 0;
}

未解决的问题

文章目录
  1. 1. 题目
  2. 2. 题意
  3. 3. 题解
  4. 4. T了的代码
  • 未解决的问题
  • {{ live2d() }}