2018年6月7日

[SDOI2014]旅行 题解

[SDOI2014]旅行 题解

题目地址：洛谷：【P3313】[SDOI2014]旅行 – 洛谷、BZOJ：Problem 3531. — [Sdoi2014]旅行

题目描述

S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。
为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件：
“CC x c“：城市x的居民全体改信了c教；
“CW x w“：城市x的评级调整为w;
“QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
“QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

题意简述

一棵树上每个点有颜色和权值，四种操作：

  1. 修改点的颜色
  2. 修改点的权值
  3. 询问路径上与起终点同色的点的权值和
  4. 询问路径上与起终点同色的点的权值最大值

保证询问的起终点同色

输入输出格式

输入格式：
输入的第一行包含整数N，Q依次表示城市数和事件数。
接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的评级和信仰。 接下来N-1行每行两个整数x，y表示一条双向道路。
接下来Q行，每行一个操作，格式如上所述。

输出格式：
对每个QS和QM事件，输出一行，表示旅行者记下的数字。

输入输出样例

输入样例#1：

5 6
3 1
2 3
1 2
3 3
5 1
1 2
1 3
3 4
3 5
QS 1 5
CC 3 1
QS 1 5
CW 3 3
QS 1 5
QM 2 4

输出样例#1：

8
9
11
3

说明

N，Q < =10^5 ， C < =10^5
数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。

题解

可以每个颜色开一棵线段树做树剖，但是空间开不下。于是我们想到了动态开点。
复杂度O(n \log^2 n)。动态开点遇到null点可以直接return减小常数。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'C' || c == 'Q';
}

inline int readop() {
    char c;
    while(!isop(c = fgc())) {}
    if(c == 'C') {
        if(fgc() == 'C') return 1;
        else return 2;
    } else {
        if(fgc() == 'S') return 3;
        else return 4;
    }
}

const int MAXN = 100005;

int n, q;

std::vector<int> gra[MAXN];

struct Node {
    int lch, rch, sum, mx;
} tr[MAXN << 8];
int rt[MAXN], tot;

inline void modify(int &o, int l, int r, int x, int v) {
    if(!o) o = ++tot;
    if(l == r) {
        tr[o].sum = tr[o].mx = v; return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) modify(tr[o].lch, l, mid, x, v);
    else modify(tr[o].rch, mid + 1, r, x, v);
    tr[o].sum = tr[tr[o].lch].sum + tr[tr[o].rch].sum;
    tr[o].mx = std::max(tr[tr[o].lch].mx, tr[tr[o].rch].mx);
}

inline int querymx(int o, int l, int r, int ll, int rr) {
    if(!o) return 0;
    if(l >= ll && r <= rr) return tr[o].mx;
    int mid = (l + r) >> 1, res = 0;
    if(ll <= mid) res = std::max(res, querymx(tr[o].lch, l, mid, ll, rr));
    if(rr > mid) res = std::max(res, querymx(tr[o].rch, mid + 1, r, ll, rr));
    return res;
}

inline int querysum(int o, int l, int r, int ll, int rr) {
    if(!o) return 0;
    if(l >= ll && r <= rr) return tr[o].sum;
    int mid = (l + r) >> 1, res = 0;
    if(ll <= mid) res += querysum(tr[o].lch, l, mid, ll, rr);
    if(rr > mid) res += querysum(tr[o].rch, mid + 1, r, ll, rr);
    return res;
}

int fa[MAXN], siz[MAXN], son[MAXN], top[MAXN], dep[MAXN], dfn[MAXN], clk;

inline void dfs1(int u) {
    siz[u] = 1;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == fa[u]) continue;
        fa[v] = u; 
        dep[v] = dep[u] + 1;
        dfs1(v);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

inline void dfs2(int u, int tp) {
    top[u] = tp; dfn[u] = ++clk;
    if(son[u]) dfs2(son[u], tp);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

inline int querymx(int x, int y, int c) {
    int res = 0, tx = top[x], ty = top[y];
    while(tx != ty) {
        if(dep[tx] > dep[ty]) {
            std::swap(x, y); std::swap(tx, ty);
        }
        res = std::max(res, querymx(rt[c], 1, n, dfn[ty], dfn[y]));
        y = fa[ty]; ty = top[y];
    }
    if(dep[x] > dep[y]) std::swap(x, y);
    res = std::max(res, querymx(rt[c], 1, n, dfn[x], dfn[y]));
    return res;
}

inline int querysum(int x, int y, int c) {
    int res = 0, tx = top[x], ty = top[y];
    while(tx != ty) {
        if(dep[tx] > dep[ty]) {
            std::swap(x, y); std::swap(tx, ty);
        }
        res += querysum(rt[c], 1, n, dfn[ty], dfn[y]);
        y = fa[ty]; ty = top[y];
    }
    if(dep[x] > dep[y]) std::swap(x, y);
    res += querysum(rt[c], 1, n, dfn[x], dfn[y]);
    return res;
}

int w[MAXN], c[MAXN], op, x, y;

int main() {
    n = readint(); q = readint();
    for(int i = 1; i <= n; i++) {
        w[i] = readint(); c[i] = readint();
    }
    for(int i = 1; i < n; i++) {
        x = readint(); y = readint();
        gra[x].push_back(y); gra[y].push_back(x);
    }
    dfs1(1);
    dfs2(1, 1);
    for(int i = 1; i <= n; i++) {
        modify(rt[c[i]], 1, n, dfn[i], w[i]);
    }
    while(q--) {
        op = readop(); x = readint(); y = readint();
        if(op == 1) {
            modify(rt[c[x]], 1, n, dfn[x], 0);
            c[x] = y;
            modify(rt[c[x]], 1, n, dfn[x], w[x]);
        } else if(op == 2) {
            w[x] = y;
            modify(rt[c[x]], 1, n, dfn[x], w[x]);
        } else if(op == 3) {
            printf("%d\n", querysum(x, y, c[x]));
        } else {
            printf("%d\n", querymx(x, y, c[x]));
        }
    }
    return 0;
}
Author:
Filed Under: 题解, 算法, 省选
Tags: , , ,

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。