《未曾设想的道路》

有根树每条边下面那个点代表的集合都是一个子树嘛，所以就是对于每个子树，求那些额外的边里面，其中一个点在子树内另外一个点在子树外的最小权值。

然后这玩意很容易想到dfs序，求出每个点入（in）和出（out）的时间戳，再把额外边的两个端点（$x_i,y_i$）改成两个点的in，然后分类讨论一下另一个点的dfs序在区间（in到out）的左边还是右边就行了。

比如在左边就变成了求：

$\min_{in_i\le x_j,x_j\le out_i,y_j\le in_i-1} val_j$

然后就变成三维偏序板子了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n, m, pos[N], tot, ans[N];
struct node
{
    int x, y, z, id, k;
} a[N];
struct edge
{
    int x, y, k;
} e[N];
struct BIT
{
    int mi[N];
    inline int lowbit(int x) { return x & -x; }
    inline void insert(int x, int k)
    {
        for (; x < N; x += lowbit(x))
            mi[x] = min(mi[x], k);
    }
    inline void erase(int x)
    {
        for (; x < N; x += lowbit(x))
            mi[x] = 2e9;
    }
    inline int query(int x)
    {
        int res = 2e9;
        for (; x; x -= lowbit(x))
            res = min(res, mi[x]);
        return res;
    }
} tr;
int head[N], to[N], val[N], nxt[N], etot, in[N], out[N], cnt;
inline void link(int u, int v, int w)
{
    to[etot] = v;
    val[etot] = w;
    nxt[etot] = head[u];
    head[u] = etot++;
}
inline void dfs(int x, int fa)
{
    in[x] = ++cnt;
    for (int i = head[x]; ~i; i = nxt[i])
        if (to[i] != fa)
            dfs(to[i], x), pos[to[i]] = val[i];
    out[x] = cnt;
}
inline void cdq(int l, int r)
{
    if (l == r)
        return;
    int mid = l + r >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    stable_sort(a + l, a + mid + 1, [](node x, node y)
                { return x.y < y.y; });
    stable_sort(a + mid + 1, a + r + 1, [](node x, node y)
                { return x.y < y.y; });
    int p = l;
    for (int i = mid + 1; i <= r; i++)
    {
        for (; p <= mid && a[p].y <= a[i].y; p++)
            if (!a[p].id)
                tr.insert(a[p].z, a[p].k);
        if (a[i].id)
            ans[a[i].id] = min(ans[a[i].id], tr.query(a[i].z));
    }
    while (p > l)
        tr.erase(a[--p].z);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(head, -1, sizeof(head));
    memset(ans, 0x3f, sizeof(ans));
    cin >> n >> m;
    for (int i = 1, u, v; i < n; i++)
        cin >> u >> v, link(u, v, i), link(v, u, i);
    dfs(1, 0);
    for (int i = 1, u, v, w; i <= m; i++)
    {
        cin >> u >> v >> w;
        e[i] = (edge){in[u], in[v], w};
        e[i + m] = (edge){in[v], in[u], w};
    }
    m <<= 1;
    for (int i = 1; i <= m; i++)
        a[++tot] = (node){-e[i].x, e[i].x, e[i].y, 0, e[i].k};
    for (int i = 2; i <= n; i++)
        a[++tot] = (node){-in[i], out[i], in[i] - 1, pos[i], 0};
    stable_sort(a + 1, a + 1 + tot, [](node x, node y)
                { return x.x == y.x ? x.y < y.y : x.x < y.x; });
    memset(tr.mi, 0x3f, sizeof(tr.mi));
    cdq(1, tot);
    tot = 0;
    for (int i = 1; i <= m; i++)
        a[++tot] = (node){-e[i].x, e[i].x, n + 2 - e[i].y, 0, e[i].k};
    for (int i = 2; i <= n; i++)
        a[++tot] = (node){-in[i], out[i], n + 2 - out[i] - 1, pos[i], 0};
    stable_sort(a + 1, a + 1 + tot, [](node x, node y)
                { return x.x == y.x ? x.y < y.y : x.x < y.x; });
    memset(tr.mi, 0x3f, sizeof(tr.mi));
    cdq(1, tot);
    for (int i = 1; i < n; i++)
        cout << (ans[i] > 1e9 ? -1 : ans[i]) << '\n';
    return 0;
}