树的统计

作者: emiya_d8a0 | 来源:发表于2018-08-13 22:06 被阅读0次

树的统计
顺序统计树
算法导论数据结构的扩张笔记
[ZJOI2008]树的统计Count
Trie树
实现 Trie
Trie树
【数据结构 & 算法】—— 高级数据结构
trie树
数据结构-Trie树

树链剖分需要注意的地方有

dfs序, 需要以重儿子优先
线段树的统计

从最初写完到最后AC一共有四处错误.

查询格式的错误, 这里的查询是线段树形式的查询, 而我是单独ql, qh;
有一句话直接复制了, 但实际是不一样的;
出现了全局变量和局部变量同名, 导致本想用全局变量时, 用成了局部变量;
应该用id数组的地方, 用成了dfn数组. 本来在讨论区看到了这个提示, 但是我却没有在意.

在调试的时候, 利用了测试数据, 认定了时QSUM函数有问题, 到最后发现时CHANG操作出现了问题, 这也是提醒.
一上午的时间和心情.

还是要注意细节

// #pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
const int MAXN = 1e5 + 600;
typedef long long ll;
using namespace std;
int n;
ll weight[MAXN];
struct Edge{
    int to, next;
} edges[MAXN << 1];
struct Segement{
    ll max, sum;
} s[MAXN << 2];
int ihead[MAXN], edgeCnt = 0;
int faz[MAXN], deep[MAXN];
int son[MAXN], size[MAXN], top[MAXN];
int id[MAXN], dfn[MAXN], tIme = 0;
int ql, qh;
ll val;
void init(){
    memset(deep, -1,sizeof(deep));
    memset(faz, -1, sizeof(faz));
}
void insert(int u, int v){
    Edge & e = edges[++edgeCnt];
    e.to = v;
    e.next = ihead[u];
    ihead[u] = edgeCnt;
}
void dfs_first(int u, int father){
    // deep[u] = deep[father] + 1;
    faz[u] = father;
    size[u] = 1;
    for(int i = ihead[u]; i; i = edges[i].next){
        Edge & e = edges[i];
        // if(e.to == father){
        if(faz[e.to] != -1){
            continue;
        }

        dfs_first(e.to, u);

        size[u] += size[e.to];
        if(size[son[u]] < size[e.to]){
            son[u] = e.to;
        }
    }
}
void dfs_second(int u, int t){
    deep[u] = deep[faz[u]] + 1;
    top[u] = t;
    id[u] = ++tIme;// id 是把树上的节点映射为区间的某一点
    dfn[tIme] = u;
    if(!son[u])
        return;

    dfs_second(son[u], t);
    for(int i = ihead[u]; i; i = edges[i].next){
        Edge & e = edges[i];
        if(e.to == son[u] || deep[e.to] != -1)
            continue;

        dfs_second(e.to, e.to);
    }
}
inline void update(int o){
    s[o].max = max(s[o << 1].max, s[o << 1 | 1].max);
    s[o].sum = s[o << 1].sum + s[o << 1 | 1].sum;
}
void build(int o, int lo, int hi){
    if(hi - lo < 2){
        s[o].sum = s[o].max = weight[dfn[lo]];
        return;
    }
    int mi = (lo + hi) >> 1;
    build(o << 1, lo, mi);
    build(o << 1 | 1, mi, hi);

    update(o);
}
void modify(int o, int lo, int hi){
    if(qh <= lo || hi <= ql)
        return;
    // if(hi - lo < 2){
    if(ql <= lo && hi <= qh){
        s[o].max = val;
        s[o].sum = val;
        return;
    }
    int mi = (lo + hi) >> 1;

    // if(ql < mi)
        modify(o << 1, lo, mi);
    // else
        modify(o << 1 | 1, mi, hi);

    update(o);
}
ll querySum(int o, int lo, int hi){
    if(qh <= lo || hi <= ql)
        return 0;
    if(ql <= lo && hi <= qh){
        return s[o].sum;
    }

    int mi = (lo + hi) >> 1;

    return querySum(o << 1, lo, mi) + querySum(o << 1 | 1, mi, hi);
}
ll queryMax(int o, int lo ,int hi){
    if(qh <= lo || hi <= ql)
        return -0x3f3f3f3f;
    if(ql <= lo && hi <= qh){
        return s[o].max;
    }

    int mi = (lo + hi) >> 1; 
    return max(queryMax(o << 1, lo, mi), queryMax(o << 1 | 1, mi, hi));
}
ll getMax(int lo, int hi){
    int fx = top[lo], fy = top[hi];
    ll rst = -0x3f3f3f3f;
    while(fx != fy){
        if(deep[fx] < deep[fy])
            swap(fx, fy), swap(lo, hi);
        ql = id[fx], qh = id[lo] + 1;// 因为查询格式写错了, 调了半天
        rst = max(rst, queryMax(1, 1, tIme));
        lo = faz[fx], fx = top[lo];
    }
    if(deep[lo] > deep[hi])
        swap(lo, hi);
    ql = id[lo], qh = id[hi] + 1;// 直接复制了循环里的话, 调了一会
    rst = max(rst, queryMax(1, 1, tIme));
    return rst;
}
ll getSum(int lo, int hi){
    int fx = top[lo], fy = top[hi];
    ll rst = 0;
    while(fx != fy){
        if(deep[fx] < deep[fy])
            swap(fx, fy), swap(lo, hi);
        ql = id[fx], qh = id[lo] + 1;
        rst += querySum(1, 1, tIme);
        lo = faz[fx], fx = top[lo];
    }
    if(deep[lo] > deep[hi])
        swap(lo, hi);
    ql = id[lo], qh = id[hi] + 1;
    rst += querySum(1, 1, tIme);
    return rst;
}
void print(int o, int lo, int hi){
    if(hi - lo < 2){
        printf(" %lld", s[o].max);
        return;
    }
    int mi = (lo + hi) >> 1;
    print(o << 1, lo, mi);
    print(o << 1 | 1, mi, hi);
}
int main(){
    init();

    int q;
    scanf("%d", &n);
    int u, v;
    for(int i = 1; i < n; ++i){
        scanf("%d%d", &u, &v);
        insert(u, v);
        insert(v, u);
    }
    for(int i = 1; i <= n; ++i){
        scanf("%lld", weight + i);
    }

    deep[0] = 0;
    dfs_first(1, 0);
    dfs_second(1, 1);

    build(1, 1, ++tIme);i]);

    scanf("%d", &q);
    char cmd[10];
    int a, b;
    while(q--){
        scanf("%s%d%d", cmd, &a, &b);
        if(cmd[0] == 'C'){
            // 修改的时候错把dfn数组当作id数组, 调了一上午
            ql = id[a];
            qh = ql + 1;
            val = b;// 开始全局变量的名字为v, 和上面的重名, 调了半天
            modify(1, 1, tIme);
        }
        else if(cmd[1] == 'M'){
            printf("%lld\n", getMax(a, b));
        }
        else if(cmd[1] == 'S'){
            printf("%lld\n", getSum(a, b));
        }
    }
    return 0;
}