Hướng dẫn cho Codeforces 383C - Giá trị lan trên cây
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Cây con và dấu theo độ sâu
Duyệt DFS từ gốc \(1\), đánh số mỗi đỉnh khi ghé lần đầu. Cây con của \(u\) chiếm đoạn đóng \([tin[u],tout[u]]\). Dùng DFS lặp vì cây có thể là một dây dài \(200\,000\) đỉnh.
Đặt \(s_u=1\) nếu độ sâu của \(u\) chẵn, và \(s_u=-1\) nếu lẻ. Khi cập nhật ở \(x\) một lượng \(val\), đỉnh \(u\) trong cây con \(x\) nhận \(s_us_xval\). Vì thế ta chỉ cần cộng \(s_xval\) lên đoạn cây con trong một mảng phụ; khi hỏi \(u\), nhân phần tăng của vị trí tin[u] với \(s_u\) rồi cộng \(a_u\) ban đầu.
Fenwick trên mảng hiệu
Để cộng \(d\) vào đoạn \([l,r]\), gọi add(l,d) và, nếu \(r<n\), gọi add(r+1,-d). Phần tăng tại vị trí \(i\) bằng prefix(i).
Vậy cập nhật ở \(x\) dùng \(d=s_xval\), còn câu hỏi ở \(u\) trả về:
Không đưa các giá trị ban đầu vào Fenwick, vì chúng đã nằm riêng trong mảng \(a\). Giá trị hiện tại có thể âm dù mọi giá trị nhập đều dương.
Vì sao dấu được đổi đúng?
Khoảng cách từ tổ tiên \(x\) xuống \(u\) có cùng tính chẵn lẻ với \(depth[u]-depth[x]\). Nếu hai độ sâu cùng tính chẵn lẻ thì \(s_us_x=1\); nếu khác thì bằng \(-1\). Mỗi cạnh đi xuống đổi tính chẵn lẻ, nên lượng tăng đổi dấu đúng như đề. Ngoài đoạn cây con không có cập nhật, nên các đỉnh khác giữ nguyên.
Tiền xử lý \(O(n)\); mỗi thao tác \(O(\log n)\), bộ nhớ \(O(n)\). Bản C++ dùng long long để giữ giá trị và các tổng trong Fenwick; bản Python cũng duyệt cây bằng ngăn xếp.
Mã tham khảo
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; if (!(cin >> n >> m)) return 0;
vector<long long> a(n + 1), bit(n + 1);
for (int i=1;i<=n;++i) cin >> a[i];
vector<vector<int>> adj(n+1);
for(int i=1,u,v;i<n;++i){cin>>u>>v;adj[u].push_back(v);adj[v].push_back(u);}
vector<int> tin(n+1),tout(n+1),sign(n+1); sign[1]=1;
vector<tuple<int,int,bool>> stack{{1,0,false}};
int timer=0;
while(!stack.empty()){
auto [u,p,leaving]=stack.back(); stack.pop_back();
if(leaving){tout[u]=timer;continue;}
tin[u]=++timer;stack.push_back({u,p,true});
for(int v:adj[u])if(v!=p){sign[v]=-sign[u];stack.push_back({v,u,false});}
}
auto add=[&](int p,long long d){for(;p<=n;p+=p&-p)bit[p]+=d;};
auto prefix=[&](int p){long long result=0;for(;p;p-=p&-p)result+=bit[p];return result;};
while(m--){
int type,x;cin>>type>>x;
if(type==1){long long val;cin>>val;val*=sign[x];add(tin[x],val);if(tout[x]<n)add(tout[x]+1,-val);}
else cout<<a[x]+sign[x]*prefix(tin[x])<<'\n';
}
}
import sys
def solve(data):
n, m = data[:2]
a = [0] + data[2:n + 2]
adj = [[] for _ in range(n + 1)]
pos = n + 2
for _ in range(n - 1):
u, v = data[pos:pos + 2]
pos += 2
adj[u].append(v)
adj[v].append(u)
tin, tout, sign = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
sign[1] = 1
timer = 0
stack = [(1, 0, False)]
while stack:
u, p, leaving = stack.pop()
if leaving:
tout[u] = timer
continue
timer += 1
tin[u] = timer
stack.append((u, p, True))
for v in adj[u]:
if v != p:
sign[v] = -sign[u]
stack.append((v, u, False))
bit = [0] * (n + 1)
answers = []
for _ in range(m):
kind, x = data[pos:pos + 2]
pos += 2
if kind == 1:
d = data[pos] * sign[x]
pos += 1
i = tin[x]
while i <= n:
bit[i] += d
i += i & -i
i = tout[x] + 1
while i <= n:
bit[i] -= d
i += i & -i
else:
value, i = 0, tin[x]
while i:
value += bit[i]
i -= i & -i
answers.append(str(a[x] + sign[x] * value))
return '\n'.join(answers) + ('\n' if answers else '')
if __name__ == '__main__':
sys.stdout.write(solve(list(map(int, sys.stdin.buffer.read().split()))))
Bình luận