Chi tiết từng bước nhảy (đúng logic code query):
1. \(depth[4]=2\), \(depth[3]=1\), \(diff=1\) → nhảy \(4\) lên \(up[4][0]=2\), \(min=2\), \(max=2\). Giờ \(u=2, v=3\) ngang nhau.
2. Xét \(j=1\): \(up[2][1]=0\) (vì \(up[2][0]=1\), \(up[1][0]=0\)), \(up[3][1]=0\) → bằng nhau nên KHÔNG nhảy (nếu nhảy cả hai sẽ rơi xuống đỉnh \(0\) vô nghĩa — đây là bẫy hay gặp).
3. Xét \(j=0\): \(up[2][0]=1\), \(up[3][0]=1\) → bằng nhau nên KHÔNG nhảy (cả hai đã là con trực tiếp của LCA \(=1\)).
4. Bước cuối: \(u=2, v=3\) là con trực tiếp của LCA → lấy 1 cạnh mỗi bên: \(\min(3,5)=3\)? Cộng với đoạn trước đó (\(4 \to 2\): \(min=2\)) → \(\min(2,3,5)=2\), \(\max(2,3,5)=5\). Kết quả \((2,5)\) khớp bảng trên.
Truy vấn 2: Max trên đường đi \(4 \to 5\) (cùng nhánh).
Bước
\(u\)
\(v\)
LCA
Max \(4 \to\) LCA
Max \(5 \to\) LCA
Kết quả
1
4
5
2
\(\max(2)=2\)
\(\max(7)=7\)
\(\max(2,7)=7\)
Truy vấn 3: Min/Max trên đường đi \(4 \to 1\) (\(1\) là gốc, \(4\) là cháu).
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(NULL);intn;cin>>n;// Số đỉnh của câyintLOG=__lg(n)+1;// Số bước nhảy tối đa: log2(N) + 1vector<vector<pair<int,int>>>adj(n+1);// Danh sách kề duy nhất: (đỉnh kề, trọng số)for(inti=0;i<n-1;i++){intu,v,w;cin>>u>>v>>w;// Đọc cạnh: u, v, trọng số wadj[u].push_back({v,w});adj[v].push_back({u,w});}vector<int>depth(n+1,0);// depth[v] = độ sâu của đỉnh vvector<vector<int>>up(n+1,vector<int>(LOG,0));// up[v][j] = tổ tiên 2^j của vvector<vector<int>>minEdge(n+1,vector<int>(LOG,INT_MAX));// min trên đoạn 2^jvector<vector<int>>maxEdge(n+1,vector<int>(LOG,INT_MIN));// max trên đoạn 2^j// BFS từ đỉnh 1 (gốc) để tính depth và up[][0], minEdge[][0], maxEdge[][0]queue<int>q;q.push(1);depth[1]=0;// Gốc có độ sâu 0while(!q.empty()){intu=q.front();q.pop();for(auto[v,w]:adj[u]){if(v==up[u][0])continue;// Bỏ qua cạnh ngược lên chadepth[v]=depth[u]+1;// Con sâu hơn cha 1 đơn vịup[v][0]=u;// Tổ tiên 2^0 của v là u (cha trực tiếp)minEdge[v][0]=w;// Min trên đoạn 1 bước = trọng số cạnhmaxEdge[v][0]=w;// Max trên đoạn 1 bước = trọng số cạnhq.push(v);}}// Binary Lifting: xây bảng up, minEdge, maxEdge cho các bước nhảy 2^jfor(intj=1;j<LOG;j++){for(inti=1;i<=n;i++){up[i][j]=up[up[i][j-1]][j-1];// Tổ tiên 2^j = tổ tiên 2^(j-1) của tổ tiên 2^(j-1)// Min/Max trên đoạn 2^j = min/max của 2 đoạn 2^(j-1) ghép lạiminEdge[i][j]=min(minEdge[i][j-1],minEdge[up[i][j-1]][j-1]);maxEdge[i][j]=max(maxEdge[i][j-1],maxEdge[up[i][j-1]][j-1]);}}// Hàm truy vấn: trả về (min, max) trên đường đi từ u đến vautoquery=[&](intu,intv)->pair<int,int>{if(depth[u]<depth[v])swap(u,v);// Đưa u xuống sâu hơn (hoặc bằng) vintmn=INT_MAX,mx=INT_MIN;intdiff=depth[u]-depth[v];// Chênh lệch độ sâu// Bước 1: đưa u lên ngang độ sâu với vfor(intj=0;j<LOG;j++){if(diff&(1<<j)){// Nếu bit j của diff = 1mn=min(mn,minEdge[u][j]);// Cập nhật min dọc đườngmx=max(mx,maxEdge[u][j]);// Cập nhật max dọc đườngu=up[u][j];// Nhảy u lên 2^j bước}}if(u==v)return{mn,mx};// u là tổ tiên của v → xong// Bước 2: nhảy cả u và v lên cùng lúc đến sát LCAfor(intj=LOG-1;j>=0;j--){if(up[u][j]!=up[v][j]){// Nếu tổ tiên 2^j khác nhaumn=min(mn,min(minEdge[u][j],minEdge[v][j]));// Cập nhật minmx=max(mx,max(maxEdge[u][j],maxEdge[v][j]));// Cập nhật maxu=up[u][j];// Nhảy u lên 2^jv=up[v][j];// Nhảy v lên 2^j}}// Bước 3: u và v là con trực tiếp của LCA → lấy 1 bước cuốimn=min(mn,min(minEdge[u][0],minEdge[v][0]));mx=max(mx,max(maxEdge[u][0],maxEdge[v][0]));return{mn,mx};};intq_count;cin>>q_count;// Số truy vấnwhile(q_count--){intu,v;cin>>u>>v;// Đọc cặp đỉnh truy vấnauto[mn,mx]=query(u,v);cout<<mn<<" "<<mx<<"\n";// In min và max trên đường đi}return0;}
fromcollectionsimportdequeimportsysinput=sys.stdin.readlinen=int(input())# Số đỉnhLOG=n.bit_length()# log2(N) làm tròn lênadj=[[]for_inrange(n+1)]# Danh sách kề (đỉnh, trọng số)for_inrange(n-1):u,v,w=map(int,input().split())# Đọc cạnh u-v có trọng số wadj[u].append((v,w))adj[v].append((u,w))depth=[0]*(n+1)# Độ sâu từ gốcup=[[0]*LOGfor_inrange(n+1)]# up[v][j] = tổ tiên 2^j của vmin_edge=[[float('inf')]*LOGfor_inrange(n+1)]# min trên đoạn 2^jmax_edge=[[float('-inf')]*LOGfor_inrange(n+1)]# max trên đoạn 2^jq=deque([1])# BFS từ đỉnh 1 (gốc)whileq:u=q.popleft()forv,winadj[u]:ifv==up[u][0]:# Bỏ qua cạnh ngược lên chacontinuedepth[v]=depth[u]+1# Con sâu hơn cha 1up[v][0]=u# Cha trực tiếp của v là umin_edge[v][0]=w# Min đoạn 1 bước = wmax_edge[v][0]=w# Max đoạn 1 bước = wq.append(v)# Binary Lifting: xây bảng cho bước nhảy 2^jforjinrange(1,LOG):foriinrange(1,n+1):up[i][j]=up[up[i][j-1]][j-1]# Nhảy 2 lần 2^(j-1)# Min/Max = ghép min/max 2 đoạn 2^(j-1)min_edge[i][j]=min(min_edge[i][j-1],min_edge[up[i][j-1]][j-1])max_edge[i][j]=max(max_edge[i][j-1],max_edge[up[i][j-1]][j-1])defquery(u,v):# Trả về (min, max) trên đường đi từ u đến vifdepth[u]<depth[v]:u,v=v,u# u là đỉnh sâu hơnmn,mx=float('inf'),float('-inf')diff=depth[u]-depth[v]# Chênh lệch độ sâu# Đưa u lên ngang vforjinrange(LOG):ifdiff&(1<<j):# Nếu bit j = 1mn=min(mn,min_edge[u][j])mx=max(mx,max_edge[u][j])u=up[u][j]# Nhảy u lên 2^jifu==v:# u trùng v → đã đến LCAreturnmn,mx# Nhảy cả u, v lên sát LCAforjinrange(LOG-1,-1,-1):ifup[u][j]!=up[v][j]:mn=min(mn,min_edge[u][j],min_edge[v][j])mx=max(mx,max_edge[u][j],max_edge[v][j])u=up[u][j]v=up[v][j]# Lấy 1 bước cuối cùng đến LCAmn=min(mn,min_edge[u][0],min_edge[v][0])mx=max(mx,max_edge[u][0],max_edge[v][0])returnmn,mxq_count=int(input())# Số truy vấnfor_inrange(q_count):u,v=map(int,input().split())# Đọc truy vấnmn,mx=query(u,v)print(mn,mx)# In min và max
// SAI (trace cũ trong bài từng mắc): u=2, v=3, thấy up[2][1] != up[3][1] là nhảy ngay// → v nhảy từ 3 xuống 0, mọi min/max sau đó đều rácif(up[u][j]!=up[v][j]){u=up[u][j];v=up[v][j];}
// ĐÚNG: với ví dụ trên, up[2][1] == up[3][1] == 0 nên KHÔNG nhảy;// chỉ nhảy khi hai tổ tiên khác nhau VÀ đều khác 0.// Khi u, v đã là con trực tiếp của LCA, vòng lặp không nhảy gì cả// mà rơi xuống "bước 3: lấy 1 cạnh cuối" trong code query.
Quy tắc nhớ: đỉnh \(0\) là "hư vô" (gốc của gốc). Mọi up[*][*] = 0 nghĩa là "đã vượt quá gốc" — không được dùng minEdge[0][*] / maxEdge[0][*] để cập nhật đáp án.
// ĐÚNG: gốc không có cạnh đi lên → min = +INF, max = -INF (trung hòa với min/max)minEdge[1][0]=INT_MAX;maxEdge[1][0]=INT_MIN;// (code khởi tạo vector đã làm đúng)