Descripción del Problema

El juego "Amor por Correr" es un simulador en el que los jugadores deben completar tareas diarias. El mapa del juego se representa como un árbol con n nodos y n-1 aristas, donde cada nodo está numerado desde 1 hasta n. Cada jugador comienza en un nodo de inicio y debe llegar a un nodo final siguiendo la ruta más corta. Los observadores en cada nodo registran cuántos jugadores pasan por su nodo en un tiempo específico.

Formato de Entrada

La primera línea contiene dos enteros, n (número de nodos) y m (número de jugadores). Las siguientes n-1 líneas contienen pares de enteros u y v, indicando una arista entre los nodos u y v. La siguiente línea contiene n enteros, donde el j-ésimo entero indica el tiempo w[j] en el que el observador en el nodo j realiza su observación. Las siguientes m líneas contienen pares de enteros s[i] y t[i], representando el nodo de inicio y el nodo final del i-ésimo jugador, respectivamente.

Formato de Salida

Se debe imprimir una línea con n enteros, donde el j-ésimo entero indica cuántos jugadores fueron observados por el observador en el nodo j.

Ejemplos de Entrada y Salida

Entrada #1``` 6 3 2 3 1 2 1 4 4 5 4 6 0 2 5 1 2 3 1 5 1 3 2 6

**Salida #1**```
2 0 0 1 1 1 

Entrada #2``` 5 3 1 2 2 3 2 4 1 5 0 1 0 3 0 3 1 1 4 5 5

**Salida #2**```
1 2 1 0 1 

Impelmentación

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 300000 + 10;
int n, m, w[MAXN];
vector<int> adj[MAXN];
int f[MAXN][25], depth[MAXN];
int ans[MAXN];

void build_tree(int u, int fa) {
    depth[u] = depth[fa] + 1;
    for (int i = 0; i <= 19; ++i) {
        f[u][i + 1] = f[f[u][i]][i];
    }
    for (int v : adj[u]) {
        if (v == fa) continue;
        f[v][0] = u;
        build_tree(v, u);
    }
}

int lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    for (int i = 20; i >= 0; --i) {
        if (depth[f[x][i]] >= depth[y]) x = f[x][i];
        if (x == y) return x;
    }
    for (int i = 20; i >= 0; --i) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

int dist(int x, int y) {
    return depth[x] + depth[y] - 2 * depth[lca(x, y)];
}

void dfs(int u) {
    for (int v : adj[u]) {
        if (v == f[u][0]) continue;
        dfs(v);
    }
    for (int i = 1; i <= m; ++i) {
        int s = point[i].u, t = point[i].v;
        if (lca(s, t) == u && depth[u] + w[u] == dist(s, u)) {
            ans[u]++;
        }
    }
}

struct Point {
    int u, v, dis;
};

Point point[MAXN];
int main() {
    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }
    build_tree(1, 0);
    for (int i = 1; i <= m; ++i) {
        int s, t;
        cin >> s >> t;
        point[i] = {s, t, dist(s, t)};
    }
    dfs(1);
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " ";
    }
    return 0;
}