洛谷 P3313 题解

admin 2021-08-04 PM 191℃ 2条

题目链接

分析

我写过的最毒瘤的 DS 题。

首先询问两点之间路径上的权值 $\max$ 和权值和。

使用树剖或者 LCT(但是我不会 LCT)。

考虑树剖。发现不同宗教在一棵树上面不太好维护。

考虑对于每一种宗教开一棵线段树。

由于空间问题使用动态开点线段树。

时空复杂度 $O(n+m)\log^2 n$。

注意:

$\color{red}{访问子节点前要判断是否为空指针}$

解决

我写过的最长的代码之一。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

template<class T>
void read(T &ret)
{
    ret = 0;
    char ch = getchar(), flag = 0;
    while ((ch < '0' || ch > '9') && ch != '-')
        ch = getchar();
    if (ch == '-')
        ch = getchar(), flag = 1;
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
    if (flag)
        ret = -ret;
}

const int N = 100005;

struct Node
{
    int w, sum, mx;
    Node *ls, *rs;
    Node(): w(0), sum(0), mx(0), ls(NULL), rs(NULL)
    {
    }
} root[N];

// 上传标记
void pushup(Node *p)
{
    p->sum = p->mx = p->w;
    if (p->ls != NULL)
    {
        p->sum += p->ls->sum;
        if (p->ls->mx > p->mx)
            p->mx = p->ls->mx;
    }
    if (p->rs != NULL)
    {
        p->sum += p->rs->sum;
        if (p->rs->mx > p->mx)
            p->mx = p->rs->mx;
    }
}

// 单点修改
// 若 val = 0 表示删除节点
// 若节点不存在则新增节点
void modify(Node *p, int l, int r, int pos, int val)
{
    if (l == r)
    {
        if (val == 0)
            delete p;
        else
            p->w = p->sum = p->mx = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
    {
        if (p->ls == NULL)
            p->ls = new Node();
        modify(p->ls, l, mid, pos, val);
        if (l == mid && val == 0)
            p->ls = NULL;
    }
    else
    {
        if (p->rs == NULL)
            p->rs = new Node();
        modify(p->rs, mid + 1, r, pos, val);
        if (mid + 1 == r && val == 0)
            p->rs = NULL;
    }
    pushup(p);
}

// 查询区间最大值
int queryMax(Node *p, int l, int r, int ql, int qr)
{
    if (ql <= l && qr >= r)
        return p->mx;
    int mid = (l + r) >> 1, ans = 0;
    if (ql <= mid && p->ls != NULL)
        ans = max(ans, queryMax(p->ls, l, mid, ql, qr));
    if (qr > mid && p->rs != NULL)
        ans = max(ans, queryMax(p->rs, mid + 1, r, ql, qr));
    return ans;
}

// 查询区间和
int querySum(Node *p, int l, int r, int ql, int qr)
{
    if (ql <= l && qr >= r)
        return p->sum;
    int mid = (l + r) >> 1, ans = 0;
    if (ql <= mid && p->ls != NULL)
        ans += querySum(p->ls, l, mid, ql, qr);
    if (qr > mid && p->rs != NULL)
        ans += querySum(p->rs, mid + 1, r, ql, qr);
    return ans;
}

// 返回第 x 棵线段树的根节点的指针
Node *tree(int x)
{
    return &root[x];
}

int head[N], ver[N << 1], nxt[N << 1], tot;
int dep[N], siz[N], son[N], top[N], id[N], fa[N], idx;
int n, q, b[N], w[N];

// 树剖预处理
void dfs1(int cur, int f)
{
    dep[cur] = dep[f] + 1, siz[cur] = 1, fa[cur] = f;
    int maxSize = -1;
    for (int i = head[cur]; i; i = nxt[i])
    {
        int to = ver[i];
        if (to == f)
            continue;
        dfs1(to, cur);
        siz[cur] += siz[to];
        if (siz[to] > maxSize)
            maxSize = siz[to], son[cur] = to;
    }
}

void dfs2(int cur, int tp)
{
    top[cur] = tp, id[cur] = ++idx;
    if (!son[cur])
        return;
    dfs2(son[cur], tp);
    for (int i = head[cur]; i; i = nxt[i])
    {
        int to = ver[i];
        if (to == fa[cur] || to == son[cur])
            continue;
        dfs2(to, to);
    }
}

void CC(int x, int c)
{
    int w = querySum(tree(b[x]), 1, n, id[x], id[x]);
    modify(tree(b[x]), 1, n, id[x], 0);
    modify(tree(c), 1, n, id[x], w);
    b[x] = c;
}

void CW(int x, int w)
{
    modify(tree(b[x]), 1, n, id[x], w);
}

int QS(int x, int y)
{
    Node *root = tree(b[x]);
    int ans = 0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        ans += querySum(root, 1, n, id[top[x]], id[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    ans += querySum(root, 1, n, id[x], id[y]);
    return ans;
}

int QM(int x, int y)
{
    Node *root = tree(b[x]);
    int ans = 0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        ans = max(ans, queryMax(root, 1, n, id[top[x]], id[x]));
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    ans = max(ans, queryMax(root, 1, n, id[x], id[y]));
    return ans;
}

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

char f()
{
    char ch = getchar();
    while (ch < 'A' || ch > 'Z')
        ch = getchar();
    return ch;
}

int main()
{
    read(n), read(q);
    for (int i = 1; i <= n; i++)
        read(w[i]), read(b[i]);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        read(x), read(y);
        addedge(x, y), addedge(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1; i <= n; i++)
        CW(i, w[i]);
    while (q--)
    {
        char op1 = f(), op2 = f();
        int x, y;
        read(x), read(y);
        if (op1 == 'Q' && op2 == 'S')
            printf("%d\n", QS(x, y));
        else if (op1 == 'Q' && op2 == 'M')
            printf("%d\n", QM(x, y));
        else if (op1 == 'C' && op2 == 'C')
            CC(x, y);
        else
            CW(x, y);
    }
    return 0;
}

非特殊说明,本博所有文章均为博主原创。

评论啦~



已有 2 条评论


  1. Xcel

    !您树剖时间复杂度是单 $\log$ /jy

    回复 2021-08-10 00:57
    1. admin 博主

      写错了 /kel 现在改了

      回复 2021-08-10 10:17