Submission #871309

#TimeUsernameProblemLanguageResultExecution timeMemory
871309TAhmed33Paths (RMI21_paths)C++98
12 / 100
61 ms11624 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 25;
vector <pair <int, int>> adj[MAXN];
int mx = 0, en = 0;
void dfs (int pos, int par, int dist) {
	if (dist >= mx) {
		mx = dist;
		en = pos;
	}
	for (auto j : adj[pos]) if (j.first != par) dfs(j.first, pos, dist + j.second);
}
int dist1[MAXN][2];
void dfs2 (int pos, int par, int dist, int c) {
	dist1[pos][c] = dist;
	for (auto j : adj[pos]) if (j.first != par) dfs2(j.first, pos, dist + j.second, c);
}
signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	dfs(1, -1, 0);
	int f1 = en;
	en = 0; mx = 0;
	dfs(f1, -1, 0);
	int f2 = en;
	dfs2(f1, -1, 0, 0);
	dfs2(f2, -1, 0, 1);
	for (int i = 1; i <= n; i++) cout << max(dist1[i][0], dist1[i][1]) << '\n';
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...