最开始没看到是全部修改完再统一查一遍，以为是树剖 + 线段树 + 卡常题。。

全部操作完之后再一起问是个很重要的性质，这告诉我们可以离线。

结合覆盖操作的特点：边上的权是它最后一次被覆盖时的权，我们可以想到：把操作全部离线下来，倒着做操作。这样，每条边在被操作之后就不会（也不能）再参与到其余的任何一次操作中了。

于是，问题转化为，每次改一条路径上边的边权，然后删掉（指不改变连通性的删）。使用树上并查集，每次更新父边之后把当前点向父亲合并即可，直到到达两点的 LCA。合并次数最多为 $n - 1$，因此复杂度是有保证的。

Solution 1

倍增求 LCA，时间复杂度 $\Theta((n + q) \log n)$。常数较大。

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

const int LOG = 20;
const int MAXN = 1e6 + 5;

vector<pair<int, int>> adj[MAXN];
int parent[MAXN], depth[MAXN], edge_id[MAXN];
int up[LOG][MAXN];
int uf[MAXN];
int ans[MAXN];
int n, q;

void build_tree() {
    queue<int> q;
    q.push(1);
    parent[1] = -1;
    depth[1] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto &[v, idx] : adj[u]) {
            if (v != parent[u]) {
                parent[v] = u;
                edge_id[v] = idx;
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
}

void preprocess_lca() {
    for (int u = 1; u <= n; ++u) {
        up[0][u] = (parent[u] == -1) ? u : parent[u];
    }
    for (int k = 1; k < LOG; ++k) {
        for (int u = 1; u <= n; ++u) {
            up[k][u] = up[k-1][up[k-1][u]];
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int k = LOG - 1; k >= 0; --k) {
        if (depth[u] - (1 << k) >= depth[v]) {
            u = up[k][u];
        }
    }
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; --k) {
        if (up[k][u] != up[k][v]) {
            u = up[k][u];
            v = up[k][v];
        }
    }
    return up[0][u];
}

int find(int u) {
    if (uf[u] != u) {
        uf[u] = find(uf[u]);
    }
    return uf[u];
}

void cover(int u, int l, int i) {
    while (true) {
        u = find(u);
        if (depth[u] <= depth[l]) break;
        ans[edge_id[u]] = i;
        int p = parent[u];
        uf[u] = find(p);
    }
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n-1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }
    build_tree();
    preprocess_lca();
    for (int u = 1; u <= n; ++u) {
        uf[u] = u;
    }
    vector<pair<int, int>> queries;
    for (int i = 0; i < q; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        queries.emplace_back(u, v);
    }
    for (int i = q; i >= 1; --i) {
        auto [u, v] = queries[i-1];
        int l = lca(u, v);
        cover(u, l, i);
        cover(v, l, i);
    }
    for (int i = 0; i < n-1; ++i) {
        printf("%d ", ans[i]);
    }
    puts("");
    return 0;
}

Solution 2

LCA 太慢了，但是只要我不断跳两个点中深度更大的点，直到两点相等就可以了。

其实能想到第 $1$ 种没啥理由想不到这种。。。

时间复杂度 $\Theta(n + q \log n)$，常数还很小。当然如果你多开个 root_in_real_tree 然后启发式合并的话可以变成 $\Theta(n + q \alpha(n))$，但是估计常数的增加会使这个优化入不敷出。读者可以自行尝试比较。

#include <cctype>
#include <cstdio>
#include <numeric>
#include <utility>
#define MAXN 1000003
using namespace std;

namespace IO
{
#define SIZ (1 << 19)
    char ibuf[SIZ], *p1 = nullptr, *p2 = nullptr;
#define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZ, stdin), p1 == p2) ? EOF : *p1++)
    void rd(int &x)
    {
        x = 0;
        char c = gc();
        while (!isdigit(c))
            c = gc();
        while (isdigit(c))
            x = x * 10 + (c ^ 48), c = gc();
    }
    template <typename... Arg>
    inline void rd(int &x, Arg &...args)
    {
        rd(x), rd(args...);
    }
    char obuf[SIZ], *p3 = obuf;
    inline void flush()
    {
        fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf;
    }
    inline void pc(const char c)
    {
        if (p3 - obuf == SIZ)
            flush();
        *p3++ = c;
    }
    void prt(int x)
    {
        static char stk[8];
        int stkp = 0;
        do
        {
            stk[stkp] = char(x % 10), x /= 10;
            ++stkp;
        } while (x);
        while (stkp)
            pc(char(stk[--stkp] + '0'));
        pc(' ');
    }
#undef gc
#undef SIZ
}
using IO::prt;
using IO::rd;

struct Edge
{
    int to, id, nxt;
} edges[MAXN << 1];
int cnt, head[MAXN], rt[MAXN], dep[MAXN], ans[MAXN];
pair<int, int> fa[MAXN], qur[MAXN];

inline void add_edge(const int from, const int to, const int id)
{
    edges[++cnt] = {to, id, head[from]}, head[from] = cnt;
}
void dfs(const int u)
{
    int f = fa[u].first;
    for (int i = head[u], to, id; i; i = edges[i].nxt)
    {
        to = edges[i].to, id = edges[i].id;
        if (to == f)
            continue;
        fa[to] = {u, id}, dep[to] = dep[u] + 1;
        dfs(to);
    }
}
int getrt(const int x)
{
    return x == rt[x] ? x : rt[x] = getrt(rt[x]);
}

int main()
{
    int n, q, u, v;
    rd(n, q);
    for (int i = 1; i < n; ++i)
        rd(u, v), add_edge(u, v, i), add_edge(v, u, i);
    dfs(1);
    for (int i = 1; i <= q; ++i)
        rd(qur[i].first, qur[i].second);
    iota(rt + 1, rt + n + 1, 1);
    for (int i = q; i; --i)
    {
        u = getrt(qur[i].first), v = getrt(qur[i].second);
        while (u != v)
        {
            if (dep[u] < dep[v])
                swap(u, v);
            ans[fa[u].second] = i, rt[u] = fa[u].first, u = getrt(rt[u]);
        }
    }
    for (int i = 1; i < n; ++i)
        prt(ans[i]);
    IO::flush();
    return 0;
}

题外话：第一份代码完全由 DeepSeek 独立思考完成。一遍过。