Truy vấn trên cây

Điểm: 1,13 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Ðược add lên bởi Khúc Anh Tuấn

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một cây gồm ~N~ nút đánh số từ ~1 \rightarrow N~. Các cạnh của cây đánh số từ ~1 \rightarrow N-1~, mỗi cạnh có trọng số là một số nguyên. Bạn cần viết chương trình thực hiện dãy các lệnh sau:

CHANGE ~i~ ~v~ ~\rightarrow~ Thay đổi trọng số của cạnh thứ ~i~ thành ~v~
NEGATE ~a~ ~b~ ~\rightarrow~ Đảo dấu trọng số của tất cả các cạnh nằm trên đường đi từ ~a~ đến ~b~
QUERY ~a~ ~b~ ~\rightarrow~ Tìm trọng số lớn nhất của các cạnh nằm trên đường đi từ ~a~ đến ~b~

Input

Input là một bộ gồm nhiều test. Dòng đầu của input là số test ~t~ ~(t \leq 20)~. Tiếp sau đó là các test.

Mỗi test bắt đầu bằng một dòng trống. Dòng tiếp theo ghi một số ~N~ ~(N \leq 10000)~. ~N-1~ dòng tiếp theo, mỗi dòng ghi ~3~ số ~a~, ~b~ và ~c~ mô tả một cạnh của cây nối ~a~ với ~b~ và có trọng số là ~c~. Thứ tự của các cạnh chính là thứ tự xuất hiện trong input. Tiếp theo là dãy các lệnh như mô tả ở trên(số lệnh không quá ~50000)~. Cuối mỗi test ghi một từ "DONE".
Dữ liệu vào luôn đảm bảo trọng số của các cạnh ở mỗi thời điểm có giá trị tuyệt đối không vượt quá ~10\,000\,000~.

Output

Với mỗi lệnh "QUERY", in ra kết quả tìm được. Nếu ~a = b~ thì ghi ra ~0~.

Sample Input

1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Sample Output

1
3

Bình luận

Hãy đọc nội quy trước khi bình luận.

7

HeroMinhSteve đã bình luận lúc 29, Tháng 7, 2025, 16:20

Bài khoai ác :') Idea vẫn là IT + HLD nhma cài khoai thật

https://ideone.com/pL305h

-7

minhduca2k53 đã bình luận lúc 18, Tháng 6, 2025, 1:21

Bài dễ phết

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

7

m1nkpk4nn đã bình luận lúc 15, Tháng 6, 2025, 6:25 ← sửa 3 →

Dành cho ai bí ý tưởng:

HLD + Lazy, code: https://ideone.com/N7cJS8

-10
phanmd đã bình luận lúc 8, Tháng 6, 2025, 9:28
Ê,có ai sai test 2 giống không vậy ,fix giúp mình với ạ

include<bits/stdc++.h>

define int long long

using namespace std; const int N = 1e4+5; struct Edge { int x,y,z; }; vector<Edge> dp; int st[4*N],s[N],d[N],h[N],p[N],c[N],r,n,T,lazy[N]; string x1;

vector<int> adj[N]; void push(int id,int l,int r) { if(lazy[id] == 0) return; st[id] = -st[id]; if(l != r) { lazy[2id] = lazy[2id]^1; lazy[2id+1] = lazy[2id+1]^1; } lazy[id] = 0; } void update(int id,int l,int r,int u,int v) { push(id,l,r); if(r < u or l > v) return; if(u <= l and r <= v) { lazy[id] = lazy[id]^1; push(id,l,r); return;

} int mid = (l+r)/2; update(2*id,l,mid,u,v); update(2*id+1,mid+1,r,u,v); st[id] = max(st[2*id],st[2*id+1]);

} long long get(int id,int l,int r,int u,int v) { push(id,l,r); if(r < u or l > v) return 0; if(u <= l and r <= v) return st[id]; int mid = (l+r)/2; return max(get(2id,l,mid,u,v),get(2id+1,mid+1,r,u,v)); } void update1(int id,int l,int r,int i,int v) { if(l > i or r < i) return; if(l == r) { st[id] = v; return; } // int mid = (l+r)/2; int mid = (l+r)/2; update1(2id,l,mid,i,v); update1(2id+1,mid+1,r,i,v); st[id] = max(st[2id],st[2id+1]); } void dfs(int u,int par) { s[u] = 1; p[u] = par; for(int v : adj[u]) { if(v == par) continue; // p[v] = u; dfs(v,u); s[u] = s[u] + s[v]; } } void dfs1(int u,int p,int t) { h[u] = t; r++; d[u] = r; long long m = 0,e = -1; for(int v : adj[u]) { if(v == p) continue; if(s[v] > m) { m = s[v]; e = v; } } if(e == -1) return; dfs1(e,u,t); for(int v : adj[u]) { if(v == p or v == e) continue; dfs1(v,u,v); } } long long ans(int u,int v) { long long ans = 0; while(h[u] != h[v]) { if(d[h[u]] < d[h[v]]) swap(u,v); ans = max(ans,get(1,1,n,d[h[u]],d[u])); u = p[h[u]]; } if(d[u] > d[v]) swap(u,v); ans = max(ans,get(1,1,n,d[u]+1,d[v])); return ans; } void truyvet(int u,int v) { while(h[u] != h[v]) { if(d[h[u]] < d[h[v]]) swap(u,v); update(1,1,n,d[h[u]],d[u]); u = p[h[u]]; } if(d[u] > d[v]) swap(u,v); update(1,1,n,d[u]+1,d[v]); } signed main() { ios::syncwithstdio(0); cin.tie(0); cout.tie(0); cin>>T; while(T--) { cin>>n; dp.clear(); r = 0; for (int i = 1; i <= n; i++) { adj[i].clear(); s[i] = d[i] = h[i] = p[i] = c[i] = 0; }

for (int i = 1; i <= 4 * n; i++) { st[i] = lazy[i] = 0; }

for(int i = 1;i < n;i++) { int x,y,z; cin>>x>>y>>z; adj[x].pushback(y); adj[y].pushback(x); dp.push_back({x,y,z}); } dfs(1,0); dfs1(1,0,1); for(int i = 0;i < dp.size();i++) { int x = dp[i].x; int y = dp[i].y; int z = dp[i].z; int l; if(p[y] == x) l = y; else l = x; c[i+1] = l; update1(1,1,n,d[l],z); } while(cin>>x1) { if(x1 == "NEGATE") { int u,v; cin>>u>>v; truyvet(u,v); } else if(x1 == "CHANGE") { int u,v; cin>>u>>v; update1(1,1,n,c[u],v); } else if(x1 == "QUERY") { int u,v; cin>>u>>v; if(u == v) cout<<0<<'\n'; else cout<<ans(u,v)<<'\n'; } if(x1 == "DONE") break; } } }
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

minhduca2k53 đã bình luận lúc 8, Tháng 6, 2025, 9:59

Chịu e ạ

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-6

vendettas đã bình luận lúc 8, Tháng 6, 2025, 14:39

chịu e ạ

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

minhduca2k53 đã bình luận lúc 18, Tháng 6, 2025, 2:04

ORz top 1 allain rank kim cương

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-12

tminh_hk20 đã bình luận lúc 11, Tháng 1, 2024, 14:47

Note: Đề bài không ràng buộc (a != b) nên khi (a==b) thì kết quả của ta =0.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-28

LeThanhMinh đã bình luận lúc 29, Tháng 12, 2022, 3:15

Sol từ cowboy coder

https://docs.google.com/document/d/1JS_4Oc7QwTiwf7LDyMk3LpQoSMeGgIjyxuhTawol8Kg/edit

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-24

ANHTUANCBN đã bình luận lúc 2, Tháng 3, 2023, 11:15

ngon

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.