• VNOJ
  • Trang chủ
  • Danh sách bài
  • Các bài nộp
  • Thành viên
    >
    • Tổ chức
  • Các kỳ thi
  • Wiki
  • Thông tin
    >
    • FAQ
    • Trình chấm ngoài
    • Tag
    • Máy chấm
    • Devlog
    • Github
    • Tickets
    • Thư viện đề thi
    • Đề xuất contest
  • Tạp chí
VI EN Đăng nhập  hoặc  Đăng ký

phammson

  • Thông tin
  • Thống kê
  • Blog

Số bài đã giải: 27
Hạng điểm: #7233
Tổng điểm: 8,85
Đóng góp: 0

Xem các bài nộp

Từ Trường THPT chuyên Lương Văn Tụy, Ninh Bình

Thông tin

include <bits/stdc++.h>

define int long long

using namespace std;

const int maxn = 50005;

vector<pair<int,int>> adj[maxn]; int d[maxn]; int res = 1e9; int u0 = 1; int sum = 0; int par[maxn]; void dfs(int u,int p){

for(auto [v,w] : adj[u]){
    if(v != p){
      par[v] = u;
      d[v] = d[u] + w;
      dfs(v,u);
    }
}
if(d[u0] < d[u]){
        u0 = u;
}

}

signed main() { // freopen("inp","r",stdin); // freopen("out","w",stdout); iosbase::syncwithstdio(0); cin.tie(0); cout.tie(0); int n; int u,v,w; cin >> n; for(int i = 0; i < n - 1; ++i){ cin >> u >> v >> w; adj[u].pushback({v,w}); adj[v].push_back({u,w}); } dfs(1,0); //cout << u0 << '\n';

memset(d, 0, sizeof d);
memset(par, 0, sizeof par);


int v0 = u0;
u0 = 0;
dfs(v0,0);
//cout << u0 << '\n';

int i = u0;
while(i != 0){
    res = min(res ,max(d[i],d[u0] - d[i]));
    i = par[i];
}
cout << res;

}

Huy hiệu

Người dùng này không có huy hiệu nào.

«    »
CN
T2
T3
T4
T5
T6
T7
Ít
Nhiều

dựa trên nền tảng DMOJ | theo dõi VNOI trên Github và Facebook