P11755 [COCI 2024/2025 #5] 树树 2 / Stablo II 题解

ELECTRODE_kaf · 2025-03-01 21:44:51 · 题解

树剖板子。痛苦卡常。

il int read() {
    int re = 0;
    char in = getchar();

    while (in < '0' || in > '9')
        in = getchar();

    while (in >= '0' && in <= '9') {
        re = re * 10 + in - 48;
        in = getchar();
    }

    return re;
}

il void print(int x) {
    if (x < 10)
        putchar(x + '0');
    else {
        print(x / 10);
        putchar(x % 10 + '0');
    }
}

const int N = 1e6 + 10;
int n, q, head[N], totedge, fa[N], top[N], dep[N], dfn[N], curdfn, siz[N], hs[N], sgtr[N * 4], lazy[N * 4];

struct edge {
    int x, y;
} nxt[N * 2];

void addedge(int x, int y) {
    totedge++;
    nxt[totedge].x = y;
    nxt[totedge].y = head[x];
    head[x] = totedge;
}

void dfs1(int p) {
    siz[p] = 1;

    for (int i = head[p]; i; i = nxt[i].y) {
        if (nxt[i].x != fa[p]) {
            fa[nxt[i].x] = p;
            dep[nxt[i].x] = dep[p] + 1;
            dfs1(nxt[i].x);
            siz[p] += siz[nxt[i].x];

            if (siz[nxt[i].x] > siz[hs[p]])
                hs[p] = nxt[i].x;
        }
    }
}

void dfs2(int p, int curtop) {
    top[p] = curtop;
    curdfn++;
    dfn[p] = curdfn;

    if (!hs[p])
        return;

    dfs2(hs[p], curtop);

    for (int i = head[p]; i; i = nxt[i].y) {
        if (nxt[i].x != fa[p] && nxt[i].x != hs[p])
            dfs2(nxt[i].x, nxt[i].x);
    }
}

void pushdown(int p) {
    sgtr[p * 2] = lazy[p];
    sgtr[p * 2 + 1] = lazy[p];
    lazy[p * 2] = lazy[p];
    lazy[p * 2 + 1] = lazy[p];
    lazy[p] = 0;
}

void upd(int p, int l, int r, int ql, int qr, int val) {
    if (ql <= l and r <= qr) {
        sgtr[p] = val;
        lazy[p] = val;
        return;
    }

    if (lazy[p])
        pushdown(p);

    int mid = (l + r) / 2;

    if (ql <= mid)
        upd(p * 2, l, mid, ql, qr, val);
    if (mid < qr)
        upd(p * 2 + 1, mid + 1, r, ql, qr, val);
}

int ans[N];

void query(int p, int l, int r) {
    if (l == r) {
        ans[l] = sgtr[p];
        return;
    }

    if (lazy[p])
        pushdown(p);

    int mid = (l + r) / 2;
    query(p * 2, l, mid);
    query(p * 2 + 1, mid + 1, r);
}

int output[N][2];

int main() {
//  cin>>n>>q;
    n = read();
    q = read();

    rep(i, 1, n - 1) {
        output[i][0] = read();
        output[i][1] = read();
        addedge(output[i][0], output[i][1]);
        addedge(output[i][1], output[i][0]);
    }

    dfs1(1);
    dfs2(1, 1);

    rep(i, 1, q) {
        int u, v;
        u = read();
        v = read();

        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]])
                swap(u, v);

//          cout << "starting upd:" << dfn[top[u]] << ' ' << dfn[u] << '\n';
//          pause;
            upd(1, 1, n, dfn[top[u]], dfn[u], i);
            u = fa[top[u]];
        }

        if (dep[u] > dep[v])
            swap(u, v);

        upd(1, 1, n, dfn[u] + 1, dfn[v], i);
//      query(1, 1, n);
//      cout << "ans:";
//
//      rep(i, 2, n) cout << ans[dfn[i]] << ' ';
//
//      endl;
//      pause;
    }

    query(1, 1, n);

    rep(i, 1, n - 1) {
        int u = output[i][0], v = output[i][1];

        if (dep[u] > dep[v]) {
            print(ans[dfn[u]]);
            putchar(' ');
        } else {
            print(ans[dfn[v]]);
            putchar(' ');
        }
    }
}