14942 개미

조건

1. 1번 방이 루트

2. 굴의 길이만큼 에너지가 소모된다

3. 불필요한 굴은 짓지 않는다 -> 각 방에서 루트까지 가는 경로는 유일하다

4. 방마다 개미는 하나만 있다.

해결법

1. dfs를 돌리는데 현재 위치까지의 경로 길이의 누적합을 저장한다.

ex) 1 - 2 - 3 - 4   로 이어지고 코스트가 각각 3,9,6이라고 한다면

     0   3   12  18 가 저장된다

2. 다음 방에 들르면서 해당 방의 개미가 가진 에너지로 어디까지 갈 수 있는지 이분탐색을 한다. (소비량이 전부 양수고 누적합이기 때문에 무조건 오름차순이 보장된다)

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
const int MV = 100000;
typedef pair<int, int> pii;
 
int n, depth, visited = 2e9;
int a[MV + 1], d[MV + 1], l[MV + 1], l2[MV + 1], s[MV + 1];
vector<pii> adj[MV + 1];
 
int bs(int x) {
    int le = 0, ri = depth, t = l[depth] - a[x], ans = depth;
    while (le <= ri) {
        int mid = (le + ri) / 2;
        if (l[mid] >= t) {
            ri = mid - 1;
            ans = mid;
        }
        else le = mid + 1;
    }
    return ans;
}
 
void dfs(int x) {
    s[x] = a[x] >= l[depth] ? 1 : l2[bs(x)];
    for (auto i : adj[x]) {
        if (d[i.first] != visited) continue;
        int nx = i.first, c = i.second;
        d[nx] = d[x] + c;
        l[++depth] = d[nx]; l2[depth] = nx;
 
        dfs(nx);
 
        l2[depth] = 0; l[depth--] = 0;
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; 
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({ v,w });
        adj[v].push_back({ u,w });
    }
    fill(d, d + n + 1, 2e9);
    d[1] = 0; l2[0] = 1;
    dfs(1);
    for (int i = 1; i <= n; i++) printf("%d\n", s[i]);
    return 0;
}