개미의 집은 N개의 방으로 tree형태로 구성되어있다.
각 방에 개미 한마리씩 있고 개미마다 가진 에너지가 주어진다.
방과 방 사이를 이동할땐 일정 에너지가 소모된다.
각 방에 있는 개미가 도달할 수 있는 방 중에 1번방과 가장 가까운 방의 번호를 구하는 문제다.
각 방에서 dfs를 돌리며 답을 찾는것은 N이 $10^5$이기 때문에 시간안에 구할 수 없다.
dfs를 한번 돌려서 1번 방으로 부터 각 방에 도달하는 에너지를 sparse table형태로 구할 수 있다.
lca에서 depth를 일치시키기 위해 $2^k$만큼 변화시켜 주듯이 풀면 $O(N*logN)$만에 구할 수 있다.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int cost[100001];
int dist[100001][19];
int par[100001][19];
vector<pair<int, int>> adj[100001];
void solve(int here, int prev) {
for (auto &n : adj[here]) {
int next = n.second;
if (next == prev) continue;
dist[next][0] = n.first;
par[next][0] = here;
solve(next, here);
}
}
void init() {
for (int m = 1;m < 19;m++) {
for (int n = 1;n <= N;n++) {
par[n][m] = par[par[n][m - 1]][m - 1];
dist[n][m] = dist[par[n][m - 1]][m - 1] + dist[n][m - 1];
}
}
}
int main() {
scanf("%d", &N);
for (int n = 1;n <= N;n++) scanf("%d", &cost[n]);
for (int n = 0;n < N - 1;n++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back({ d,v });
adj[v].push_back({ d,u });
}
solve(1, -1);
init();
for (int n = 1;n <= N;n++) {
int here = n;
for (int m = 18;m >= 0;m--) {
if (cost[n] - dist[here][m] >= 0) {
cost[n] -= dist[here][m];
here = par[here][m];
}
}
printf("%d\n", here == 0 ? 1 : here);
}
return 0;
}
| cs |
