WA 30pts 求条
查看原帖
WA 30pts 求条
574849
biyi_mouse楼主2025/1/7 18:26
#include <bits/stdc++.h>
using namespace std;
const int N = 80010, M = 500010;
int n, p, Q;

int len;
struct Query {
    int op, x, l, r, v, k, id; 
    bool operator < (const Query &t) const {
        return x < t.x || x == t.x && op < t.op;
    }
} q[M], q1[M], q2[M];

struct BST {
    int tr[N];
    inline int lowbit(int x) {
        return x & -x;
    } 
    void add(int x, int k) {
        for (; x <= n; x += lowbit(x)) tr[x] += k;
    }
    int query(int x) {
        int res = 0;
        for (; x; x -= lowbit(x)) res += tr[x];
        return res;
    }
} btree;

int h[N], e[N], ne[N], idx, in[N];
int fa[N][22], depth[N];
int dfn[N], st[N], ed[N], cnt;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs(int root) {
    queue<int> q; q.push(root);
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    while (q.size()) {
        int t = q.front(); q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                q.push(j);
                for (int k = 1; k < 21; k ++) fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}
void dfs(int u, int fa) {
    dfn[++ cnt] = u, st[u] = cnt;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
    }
    dfn[++ cnt] = u, ed[u] = cnt;
}
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 20; k >= 0; k --)
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 20; k >= 0; k --)
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }  
    return fa[a][0];
}
int getson(int u, int father) {
    for (int i = 20; i >= 0; i --)
        if (depth[fa[u][i]] > depth[father]) u = fa[u][i];
    return u;
}

int alls[N], ans[N]; 
void solve(int l, int r, int L, int R) {
    if (l > r) return;
    if (L == R) {
        for (int i = l; i <= r; i ++)
            if (q[i].op) ans[q[i].id] = alls[L];
        return;
    }
    int mid = L + R >> 1, k1 = 0, k2 = 0;
    for (int i = l; i <= r; i ++) {
        if (!q[i].op) {
            if (q[i].k <= mid) {
                btree.add(q[i].l, q[i].v); btree.add(q[i].r + 1, -q[i].v);
                q1[++ k1] = q[i];
            } else {
                q2[++ k2] = q[i];
            }
        } else {
            int t = btree.query(q[i].l);
            if (t >= q[i].k) q1[++ k1] = q[i];
            else q[i].k -= t, q2[++ k2] = q[i]; 
        }
    }
    for (int i = 1; i <= k1; i ++) q[l + i - 1] = q1[i];
    for (int i = 1; i <= k2; i ++) q[l + i + k1 - 1] = q2[i];
    solve(l, l + k1 - 1, L, mid); solve(l + k1, r, mid + 1, R);
}

int main() {
    scanf("%d%d%d", &n, &p, &Q);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++) {
        int a, b; scanf("%d%d", &a, &b);
        add(a, b); add(b, a);
    }
    bfs(1); dfs(1, -1);

    for (int i = 1; i <= p; i ++) {
        int x, y, c; scanf("%d%d%d", &x, &y, &c); alls[i] = c;
        if (st[x] > st[y]) swap(x, y);
        int LCA = lca(x, y);
        if (LCA != x) {
            q[++ len] = {0, st[x], st[y], ed[y], 1, c, 0};
            q[++ len] = {0, ed[x] + 1, st[y], ed[y], -1, c, 0};
        } else {
            int z = getson(y, x);
            if (st[z] > 1) {
                q[++ len] = {0, 1, st[y], ed[y], 1, c, 0};
                q[++ len] = {0, st[z], st[y], ed[y], -1, c, 0};                                 
            } 
            if (ed[z] < n) {
                q[++ len] = {0, st[y], ed[z] + 1, n, 1, c, 0};
                q[++ len] = {0, ed[y] + 1, ed[z] + 1, n, -1, c, 0};
            }
        }
    }

    sort(alls + 1, alls + 1 + p);
    int m = unique(alls + 1, alls + 1 + p) - alls - 1;
    for (int i = 1; i <= len; i ++) q[i].k = lower_bound(alls + 1, alls + 1 + m, q[i].k) - alls;

    for (int i = 1; i <= Q; i ++) {
        int u, v, k; scanf("%d%d%d", &u, &v, &k);
        if (st[u] > st[v]) swap(u, v);
        q[++ len] = {1, st[u], st[v], 0, 0, k, i};
    }

    sort(q + 1, q + 1 + len);
    solve(1, len, 1, m);
    for (int i = 1; i <= Q; i ++) printf("%d\n", ans[i]);
    return 0;
}
2025/1/7 18:26
加载中...