给定一棵包含N个节点的带权树，节点编号1~N。小Hi每次会给定树上两个节点的编号u和v，请你计算从u到v的路径上，哪条边的权值最小。

请你输出最小的权值。

输入
第一行包含两个整数N和Q，代表节点数和询问次数。

以下N行每行包含一个整数Pi, Wi，代表1~N的父节点的编号，以及(i, P[i])这条边的权值。其中根的父节点编号为0，这一行的Wi也为0。

以下Q行每行包含两个整数u和v，代表一个询问。

1 <= N, Q <= 100000 1 <= u, v <= N 0 <= Wi <= 1000000000

题解：求树上的两点间的最小值，我们可以想求出两点间的LCA，然后倍增的求出

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int head[maxn], tot;
int lg[maxn + 5];
int depth[maxn + 5], dp[maxn][22];
int father[maxn + 5][22];
int p[maxn], w[maxn];
int n, m, x;
struct Edge {
    int u, v, w, next;
}edge[maxn];

void init() {
    memset(head, -1, sizeof(head)); tot;
}

void add(int u, int v, int w) {
    edge[++tot].u = u; 
    edge[tot].w = w;
    edge[tot].v = v; 
    edge[tot].next = head[u]; head[u] = tot;
}

void dfs(int u, int fa) { //dfs预处理
    depth[u] = depth[fa] + 1;
    father[u][0] = fa;
    for(int j = 1; j <= lg[depth[u]] + 1; j++) {
        father[u][j] = father[father[u][j - 1]][j - 1];
        dp[u][j] = min(dp[u][j - 1], dp[father[u][j - 1]][j - 1]);
    }
    for (int i = head[u]; i  != -1; i = edge[i].next) {
        int to = edge[i].v;
        if (to == fa) {
            continue;
        }
        dp[to][0] = edge[i].w;
        dfs(to, u);
    }
}
int LCA(int u, int v) { //求LCA
    if(depth[u] < depth[v]) {
        swap(u, v);
    }
    while(depth[u] != depth[v]) {
        u = father[u][lg[depth[u] - depth[v]]];
    }
    if(u == v) {
        return u;
    }
    for(int j = lg[depth[u]]; j >= 0; j--) {
        if(father[u][j] != father[v][j]) {
            u = father[u][j];
            v = father[v][j];
        }
    }
    return father[u][0];
}

int getAns(int u, int lca) { //每次都进行一次倍增zhi'dao
    int k = lg[depth[u] - depth[lca]];
    if (father[u][k] == lca) return dp[u][k];
    return min(dp[u][k], getAns(father[u][k], lca));

}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    init();
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i], &w[i]);
        add(i, p[i], w[i]); add(p[i], i, w[i]);
    }
    dfs(0, 0);
    int u, v;
    while (m--) {
        scanf("%d%d", &u, &v);
        if (u == v) {
            printf("0\n"); continue;
        }
        int lca = LCA(u, v);
        if (lca == u) {
            int k = lg[depth[v] - depth[lca]];
            printf("%d\n", getAns(v, lca));
        } else if (lca == v) {
            printf("%d\n", getAns(u, lca));
        } else {
            printf("%d\n", min(getAns(u, lca), getAns(v, lca)));
        }
    }
    return 0;
}