Solutions of Tree diameter

Select solution language

P3t3r Created at 11 likes

Use BFS from any node to find the maximum distance from that node Then from the node we got the maximum distance, we use BFS to find the maximum distance from that node In conclusion we use 2 BFS

sharinganvanhoadong Created at 0 likes

- **HINT:** Xét $1$ gốc để lan $BFS$ xác định cây. Hãy sử dụng tham lam để xem $2$ đỉnh cách xa nhau nhất khi nào. #**HƯỚNG DẪN:**<br> - $2$ đỉnh cách xa nhau nhất là $2$ đỉnh đuôi của $2$ nhánh cây dài nhất (cách xa gốc nhất)(vì đỉnh này phải đi qua gốc để tới đỉnh kia).<br> - Chú ý trong gốc cây lớn còn có gốc của cây con (các đỉnh mà tách ra làm $2$ nhánh tiếp theo, tức là bậc $3$ do có cả nhánh nối từ gốc lớn tới đỉnh đó.)<br> $+$ Xét gốc cây con, ta lại $BFS$ cây con đó, tạo $1$ queue mới nhưng vẫn sử dụng mảng đếm cũ, do tạo thêm sẽ mất rất nhiều bộ nhớ $+$ thời gian.(ta có thể sd ngay mảng đếm của cây con trùng vào mảng đếm của cây lớn)<br> ##**CODE MẪU:** ```cpp #include<iostream> #include<queue> #include<vector> using namespace std; int n,m,x,y,frt,ans,cnt[100005],deg[100005]; queue<int>qe; vector<int>dske[100005]; int bfs(int x) { queue<int> qe; int frt,nhat=-1,nhi=-1,mx=-1; cnt[x]=0; qe.push(x); while(!qe.empty()) { frt=qe.front(); for(int i:dske[frt]) { if(cnt[i]==-1)//nhieu cai && qua thi if chung luon. { cnt[i]=cnt[frt]+1; if(deg[i]==2) { qe.push(i); } else if(deg[i]==1) { if(cnt[i]>nhat) nhi=nhat,nhat=cnt[i]; else if(cnt[i]>nhi) nhi=cnt[i]; } else { mx=bfs(i)+cnt[frt]+1; if(mx>nhat) nhi=nhat,nhat=mx; else if(mx>nhi) nhi=mx; } } } qe.pop(); } ans=max(ans,nhat+nhi); return nhat; } int main() { cin>>n; if(n==1) { cout<<0; return 0; } if(n==2) { cout<<1; return 0; } fill(cnt+1,cnt+n+1,-1); for(int i=1;i<n;i++) { cin>>x>>y; dske[x].push_back(y); dske[y].push_back(x); deg[x]++; deg[y]++; } for(int i=1;i<=n;i++) { if(deg[i]>1) { bfs(i); cout<<ans; return 0; } } } ```