The Preliminary Contest for ICPC China Nanchang National Invitational-J.Distance on the tree(树上主席树)

题目链接:The Preliminary Contest for ICPC China Nanchang National Invitational-J.Distance on the tree

题意:

给一棵树,q个询问,询问由u点到v点的路径上有多少条边的边权小于等于w。

题解:

树上建主席树。

答案等于query(u)+query(v)-2*query(lca)。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m;
struct EDGE
{
    int v, nxt, w;

} edge[MAXN << 1];
struct QEDGE
{
    int u, v, w, nxt, lca;
} qedge[MAXN << 1];
int ecnt = 0, fir[MAXN], qcnt, qfir[MAXN];
void addedge(int u, int v, int w)
{
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
void add_qedge(int u, int v, int w)
{
    qedge[qcnt].u = u;
    qedge[qcnt].v = v;
    qedge[qcnt].w = w;
    qedge[qcnt].nxt = qfir[u];
    qfir[u] = qcnt++;
}
//求LCA
int fa[MAXN];
bool used[MAXN];
int getf(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = getf(fa[x]);
}
void tarjan(int u)
{
    fa[u] = u;
    used[u] = 1;
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        if (!used[v])
        {
            tarjan(v);
            fa[v] = u;
        }
    }
    for (int i = qfir[u]; i != -1; i = qedge[i].nxt)
    {
        int v = qedge[i].v;
        if (used[v])
        {
            qedge[i].lca = getf(v);
            qedge[i ^ 1].lca = qedge[i].lca;
        }
    }
}
int tot = 0;
int Tree[MAXN * 40];
int ls[MAXN * 40], rs[MAXN * 40], sum[MAXN * 40];
void update(int las, int val, int l, int r, int &rt)
{
    rt = ++tot;
    ls[rt] = ls[las];
    rs[rt] = rs[las];
    sum[rt] = sum[las] + 1;
    if (l == r)
        return;
    int mid = (1ll * (1ll * l + 1ll * r)) >> 1;
    if (val <= mid)
        update(ls[las], val, l, mid, ls[rt]);
    else
        update(rs[las], val, mid + 1, r, rs[rt]);
}
int query(int l, int r, int rot, int k)
{
    //cout << "fuck" << endl;
    if (l == r)
        return sum[rot];
    int mid = (1ll * l + r) >> 1;
    if (k <= mid)
        return query(l, mid, ls[rot], k);
    else
        return sum[ls[rot]] + query(mid + 1, r, rs[rot], k);
}
void dfs(int u, int FA)
{
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        int w = edge[i].w;
        if (v == FA)
            continue;
        update(Tree[u], w, 0, inf, Tree[v]);
        dfs(v, u);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    ecnt = qcnt = 0;
    memset(fir, -1, sizeof(fir));
    memset(qfir, -1, sizeof(qfir));
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_qedge(u, v, w);
        add_qedge(v, u, w);
    }

    tarjan(1);
    dfs(1, -1);
    for (int i = 0; i < m; i++)
    {
        int num = i * 2;
        int u = qedge[num].u, v = qedge[num].v, w = qedge[num].w, lca = qedge[num].lca;
        printf("%d\n", query(0, inf, Tree[u], w) + query(0, inf, Tree[v], w) - 2 * query(0, inf, Tree[lca], w));
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。