Hellc

【题目描述】

见 UOJ 好咯。

【题目链接】

UOJ 58 糖果公园 【WC 2013】

BZOJ 3052 糖果公园

【解题思路】

树上带修改莫队，详见 莫队算法 - 学习笔记

【AC代码】

祝大家一遍 A 掉，反正我没能做到，还好我做这题时没啥人...

#include <cstdio>
#include <algorithm>
#include <cmath>

namespace io{
    const int INSIZE = 1 << 15, OTSIZE = 1 << 20;
    char inBuf[INSIZE], otBuf[OTSIZE], *S, *T, ch;
    int now;

    inline void init(){
        S = T = NULL;
        now = 0;
    }

    inline int getchar(){
        if(S == T) S = inBuf, T = inBuf + fread(inBuf, 1, INSIZE, stdin);
        if(S == T) return EOF;
        return *S++;
    }

    template<typename Int>
    inline void readint(Int &x){
        Int f = 1;
        for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
        for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
        x *= f;
    }

    inline void flush(){
        if(now) fwrite(otBuf, 1, now, stdout), now = 0;
    }

    inline void putchar(char ch){
        otBuf[now++] = ch;
        if(now == OTSIZE) flush();
    }

    template<typename Int>
    inline void putint(Int x){
        if(x < 0) putchar('-'), putint(-x);
        else{
            if(x > 9) putint(x / 10);
            putchar(x % 10 + '0');
        }
    }

    inline void br(){
        putchar('\n');
    }

    inline void close(){
        flush();
    }
}

typedef long long int64;

const int MAXN = 100000;
const int MAXM = 100000;
const int MAXL = 2 * MAXN - 1;
const int MAXLOGL = 18;
const int MAXQ = 100000;

struct Node{
    struct Edge *edges;
    Node *fa;

    int candy;

    int id, pos, blockId, depth;
    bool in;
} nodes[MAXN];

struct Edge{
    Node *to;
    Edge *next;

    Edge() {}
    Edge(Node *fr, Node *to) : to(to), next(fr->edges) {}
} epool[2 * (MAXN - 1)], *eptr = epool;

inline void link(Node *u, Node *v){
    u->edges = new (eptr++) Edge(u, v);
    v->edges = new (eptr++) Edge(v, u);
}

int n, m, q;

int value[MAXM + 1], curiosity[MAXN + 1];

int64 ans[MAXM];

Node *f[MAXL][MAXLOGL + 1];
int logBase2[MAXL + 1];
int len;

Node *S[MAXN];
int top;
int blockCnt, blockSize;

inline void dfs(Node *v, Node *fa = NULL){
    static int dfsClock = 0;
    v->id = ++dfsClock;

    f[v->pos = len++][0] = v;

    int bot = top;
    for(Edge *e = v->edges; e; e = e->next) if(!e->to->depth){
        e->to->depth = v->depth + 1, e->to->fa = v, dfs(e->to);
        if(top - bot >= blockSize){
            while(top > bot) S[--top]->blockId = blockCnt;
            blockCnt++;
        }

        f[len++][0] = v;
    }

    S[top++] = v;
}

inline Node* min(Node *a, Node *b){
    return a->depth < b->depth ? a : b;
}

inline Node* rmq(int l, int r){
    int k = logBase2[r - l + 1];
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}

inline Node* queryLCA(Node *a, Node *b){
    if(a->pos > b->pos) std::swap(a, b);
    return rmq(a->pos, b->pos);
}

void build(){
    blockSize = int(std::ceil(std::pow(n, 2.0 / 3.0) + 1e-6));
    nodes->depth = 1, nodes->fa = NULL, dfs(nodes);
    while(top) S[--top]->blockId = blockCnt - 1;

    logBase2[1] = 0;
    for(int i = 2; i <= len; i++) logBase2[i] = logBase2[i >> 1] + 1;
    
    for(int k = 1; k <= logBase2[len]; k++){
        for(int i = 0; i < len; i++){
            if(i + (1 << k - 1) < len){
                f[i][k] = min(f[i][k - 1], f[i + (1 << k - 1)][k - 1]);
            } else{
                f[i][k] = f[i][k - 1];
            }
        }
    }
}

struct Modification{
    Node *pos;
    int candy;
} modifications[MAXQ];

struct Query{
    Node *u, *v;
    int id, time;

    inline friend bool operator<(const Query &a, const Query &b){
        if(a.u->blockId != b.u->blockId) return a.u->blockId < b.u->blockId;
        else if(a.v->blockId != b.v->blockId) return a.v->blockId < b.v->blockId;
        else return a.time < b.time;
    }
} querys[MAXQ];

int mcnt, qcnt;

int buc[MAXN];
int64 currAns;

inline int64 contribution(int candy){
    return (int64)value[candy] * curiosity[ buc[candy] ];
}

inline void flip(Node *v){
    v->in ^= 1;
    if(v->in){
        ++buc[v->candy];

        currAns += contribution(v->candy);
    } else{
        currAns -= contribution(v->candy);

        --buc[v->candy];
    }
}

inline void flip(Node *u, Node *v){
    Node *lca = queryLCA(u, v);
    for(Node *p = u; p != lca; p = p->fa) flip(p);
    for(Node *p = v; p != lca; p = p->fa) flip(p);
}

inline void flipModification(int time){
    Modification *o = modifications + time;

    bool in = o->pos->in;

    if(in) flip(o->pos);
    std::swap(o->candy, o->pos->candy);
    if(in) flip(o->pos);
}

inline void solve(){
    std::sort(querys, querys + qcnt);

    Node *u = nodes, *v = nodes, *lca = nodes;
    flip(nodes);
    int currTime = 0;
    for(Query *q = querys; q != querys + qcnt; q++){
        while(currTime < q->time) flipModification(currTime++);
        while(currTime > q->time) flipModification(--currTime);

        flip(lca);
        lca = queryLCA(q->u, q->v);
        flip(lca);

        flip(u, q->u), u = q->u;
        flip(v, q->v), v = q->v;

        ans[q->id] = currAns;
    }
}

int main(){
    io::init();

    io::readint(n), io::readint(m), io::readint(q);
    for(int i = 1; i <= m; i++) io::readint(value[i]);
    for(int i = 1; i <= n; i++) io::readint(curiosity[i]);
    for(int i = 0, u, v; i < n - 1; i++){
        io::readint(u), io::readint(v), u--, v--;

        link(nodes + u, nodes + v);
    }
    for(Node *v = nodes; v != nodes + n; v++) io::readint(v->candy);

    build();

    for(int i = 0; i < q; i++){
        int t;
        io::readint(t);

        if(t == 1){ // Query
            Query *q = querys + qcnt;

            int u, v;
            io::readint(u), io::readint(v), u--, v--;
            q->u = nodes + u, q->v = nodes + v, q->id = qcnt, q->time = mcnt;

            if(q->v->id > q->u->id) std::swap(q->u, q->v);

            qcnt++;
        } else if(t == 0){ // Modification
            Modification *o = modifications + mcnt;

            int pos, candy;
            io::readint(pos), io::readint(candy), pos--;
            o->pos = nodes + pos, o->candy = candy;

            mcnt++;
        } else{
            throw;
        }
    }

    solve();

    for(int i = 0; i < qcnt; i++) io::putint(ans[i]), io::br();

    io::close();
    return 0;
}

就是这样咯~