21 Days Training // Day 16

T1. tree

My idea : BF.

Directly jumps K steps from the start node, record the maximum and the mininum value.

Code :

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    int N;cin >> N;
    int W[N];
    for (int i=0;i<N;i++) cin >> W[i];
    map<int, int> par;
    for (int i=0;i<N-1;i++) {
        int v, u;cin >> v >> u;
        par[v] = u;
    }
    int Q;cin >> Q;
    for (int i=0;i<Q;i++) {
        int u, k;cin >> u >> k;
        int mx=W[u-1], mn=W[u-1];
        int bk=u;
        for (int i=0;i<k-1;i++) {
            bk = par[bk];
            mx = max(mx, W[bk-1]);
            mn = min(mn, W[bk-1]);
        }
        if (mx==W[u-1]) cout << 0;
        else cout << mx-mn;
        cout << endl;
    }
    return 0;
}

Complexity : O(n^2)
Expected : 10/30