洛谷P2590-树的统计(树链剖分+线段树)

题目链接:洛谷P2590-树的统计

题意:

已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:

  1. CHANGE u t 表示把u点点权改为t。
  2. QMAX u v 询问u点到v点路径上的节点的最大权值。
  3. QSUM u v 询问u点到v点路径上节点的权值和。

题解:

树链剖分。

参考代码:

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
int n, q;
int a[MAXN];
struct EDGE
{
    int v, nxt;
} edge[MAXN << 1];
int fir[MAXN], ecnt = 0;
IL void addedge(int u, int v)
{
    edge[ecnt].v = v;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
int dfscnt;
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN], rk[MAXN], id[MAXN], top[MAXN];
int mx[MAXN << 2], sum[MAXN << 2];
IL void seg_pushup(int rt)
{
    mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
IL void seg_build(int l, int r, int rt)
{
    mx[rt] = 0, sum[rt] = 0;
    if (l == r)
    {
        mx[rt] = sum[rt] = a[rk[l]];
        return;
    }
    int mid = (l + r) >> 1;
    seg_build(l, mid, rt << 1);
    seg_build(mid + 1, r, rt << 1 | 1);
    seg_pushup(rt);
}
IL void seg_update(int pos, int val, int l, int r, int rt)
{
    if (l == r && l == pos)
    {
        mx[rt] = sum[rt] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        seg_update(pos, val, l, mid, rt << 1);
    else
        seg_update(pos, val, mid + 1, r, rt << 1 | 1);
    seg_pushup(rt);
}
IL int seg_query_sum(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return sum[rt];
    int mid = (l + r) >> 1;
    int res = 0;
    if (L <= mid)
        res += seg_query_sum(L, R, l, mid, rt << 1);
    if (R > mid)
        res += seg_query_sum(L, R, mid + 1, r, rt << 1 | 1);
    return res;
}
IL int seg_query_max(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return mx[rt];
    int mid = (l + r) >> 1;
    int res = -1e9;
    if (L <= mid)
        res = max(res, seg_query_max(L, R, l, mid, rt << 1));
    if (R > mid)
        res = max(res, seg_query_max(L, R, mid + 1, r, rt << 1 | 1));
    return res;
}
IL void dfs1(int u, int Fa, int depth)
{
    fa[u] = Fa, dep[u] = depth, sz[u] = 1;
    int maxson = -1;
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        if (v == Fa)
            continue;
        dfs1(v, u, depth + 1);
        sz[u] += sz[v];
        if (sz[v] > maxson)
            son[u] = v, maxson = sz[v];
    }
}
IL void dfs2(int u, int t)
{
    top[u] = t;
    id[u] = ++dfscnt;
    rk[dfscnt] = u;
    if (son[u] == -1)
        return;
    dfs2(son[u], t);
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        if (v != fa[u] && v != son[u])
            dfs2(v, v);
    }
}
IL int query_sum(int x, int y)
{
    int res = 0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        res += seg_query_sum(id[top[x]], id[x], 1, n, 1);
        x = fa[top[x]];
    }
    if (id[x] > id[y])
        swap(x, y);
    res += seg_query_sum(id[x], id[y], 1, n, 1);
    return res;
}
IL int query_max(int x, int y)
{
    int res = -1e9;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        res = max(res, seg_query_max(id[top[x]], id[x], 1, n, 1));
        x = fa[top[x]];
    }
    if (id[x] > id[y])
        swap(x, y);
    res = max(res, seg_query_max(id[x], id[y], 1, n, 1));
    return res;
}
int main()
{
    scanf("%d", &n);
    ecnt = 0;
    memset(fir, -1, sizeof(fir));
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v), addedge(v, u);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    memset(son, -1, sizeof(son));
    dfs1(1, -1, 1);
    dfs2(1, 1);
    seg_build(1, n, 1);
    scanf("%d", &q);
    while (q--)
    {
        char op[10];
        int x, y;
        scanf("%s", op);
        scanf("%d%d", &x, &y);
        if (op[0] == 'Q')
        {
            if (op[1] == 'M')
                printf("%d\n", query_max(x, y));
            else
                printf("%d\n", query_sum(x, y));
        }
        else
            seg_update(id[x], y, 1, n, 1);
    }
    return 0;
}

发表留言

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