题解 P4074 【[WC2013]糖果公园】

题目链接

Solution [WC2013]糖果公园

题目大意:多次询问树上路径权值(计算方法题目已给出),带修改可离线

分析:这题可谓集各种莫队算法于一身()

首先,观察计算路径权值

\(\sum_cval[c] \sum_{i =1}^{cnt[c]}w[c]\)

\(val\)表示美味指数,\(cnt\)表示出现次数,\(w\)表示新鲜指数

显然无论增加还是减少点,对答案的影响都是可以\(O(1)\)求的

然后树上莫队就好了

既然是莫队,本质上还是一个暴力,朴素莫队对序列分块,这里对树进行分块

[SCOI2005]王室联邦这题就是给树分块的板子题

然后套用莫队思想,只不过和序列上的莫队有点区别

朴素莫队可以直接在序列上跳\(l\),\(r\)指针,这里跳的方式有点不同

设当前的记录\(u,v\)这条路径上的答案,我们要求\(tu,tv\)路径上的答案,假如直接消除\(u,v\)再加入\(tu,tv\)就和暴力没有任何区别

我们可以翻转\(u,tu\)路径和\(v,tv\)路径,也就是把出现过的删掉,没出现过的加进去(\(LCA\)这玩意儿比较烦,单独处理),具体证明可以看这位巨佬的\(blog\)

待修莫队记个时间戳就好,块大小\(n^{\frac{2}{3}}\)

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100,maxdep = 25;
inline int read(){
    int x = 0;char c = getchar();
    while(!isdigit(c))c = getchar();
    while(isdigit(c))x = x * 10 + c - '0',c = getchar();
    return x;
}
vector<int> G[maxn];
stack<int> stk;
inline void addedge(int from,int to){G[from].push_back(to);};
int dep[maxn],faz[maxn][maxdep + 1],col[maxn],v[maxn],w[maxn],vis[maxn],cnt[maxn],val[maxn],n,m,q,siz,col_tot,ques_tot,nowu,nowv,nowtim;
ll ans[maxn],tmpans;
inline void dfs(int u){
    int tmp = stk.size();
    dep[1] = 1;
    for(int i = 1;i <= maxdep;i++)
        faz[u][i] = faz[faz[u][i - 1]][i - 1];
    for(int v : G[u]){
        if(v == faz[u][0])continue;
        dep[v] = dep[u] + 1;
        faz[v][0] = u;
        dfs(v);
        if(stk.size() - tmp >= siz){
            col_tot++;
            while(stk.size() != tmp)col[stk.top()] = col_tot,stk.pop();
        }
    }
    stk.push(u);
}
inline int lca(int x,int y){
    if(dep[x] < dep[y])swap(x,y);
    for(int i = maxdep;i >= 0;i--)
        if(dep[faz[x][i]] >= dep[y])x = faz[x][i];
    if(x == y)return x;
    for(int i = maxdep;i >= 0;i--)
        if(faz[x][i] != faz[y][i])
            x = faz[x][i],y = faz[y][i];
    return faz[x][0];
}
inline void rev(int u){//翻转点
    if(vis[u]) tmpans -= (ll)v[val[u]] * w[cnt[val[u]]--];
    else tmpans += (ll)v[val[u]] * w[++cnt[val[u]]];
    vis[u] ^= 1;
}
inline void modify(int x,int y){//翻转路径
    if(dep[x] < dep[y])swap(x,y);
    while(dep[faz[x][0]] >= dep[y])
        rev(x),x = faz[x][0];
    while(x != y)
        rev(x),rev(y),x = faz[x][0],y = faz[y][0];
}
struct Modi{
    int pos,from,to;
}modi[maxn];
inline void add_modi(int tim){
    Modi tmp = modi[tim];bool flag = false;
    if(vis[tmp.pos])flag = true,rev(tmp.pos);
    val[tmp.pos] = tmp.to;
    if(flag)rev(tmp.pos);
}
inline void del_modi(int tim){
    Modi tmp = modi[tim];bool flag = false;
    if(vis[tmp.pos])flag = true,rev(tmp.pos);
    val[tmp.pos] = tmp.from;
    if(flag)rev(tmp.pos);
}
struct Ques{
    int u,v,tim,id;
    bool operator < (const Ques &rhs)const{
        if(col[u] != col[rhs.u])return col[u] < col[rhs.u];
        if(col[v] != col[rhs.v])return col[v] < col[rhs.v];
        return tim < rhs.tim;
    }
}ques[maxn];
int main(){
    n = read(),m = read(),q = read();
    siz = pow(n,0.66);
    for(int i = 1;i <= m;i++)v[i] = read();
    for(int i = 1;i <= n;i++)w[i] = read();
    for(int u,v,i = 1;i < n;i++)
        u = read(),v = read(),addedge(u,v),addedge(v,u);
    dfs(1);
    for(int i = 1;i <= n;i++)
        val[i] = read();
    for(int opt,x,y,i = 1;i <= q;i++){
        opt = read(),x = read(),y = read();
        if(!opt)modi[++nowtim] = Modi{x,val[x],y},val[x] = y;
        else ques_tot++,ques[ques_tot] = Ques{x,y,nowtim,ques_tot};
    }
    sort(ques + 1,ques + 1 + ques_tot);
    nowu = nowv = 1;
    for(int i = 1;i <= ques_tot;i++){
        while(nowtim < ques[i].tim)add_modi(++nowtim);
        while(nowtim > ques[i].tim)del_modi(nowtim--);
        modify(nowu,ques[i].u);
        modify(nowv,ques[i].v);
        nowu = ques[i].u,nowv = ques[i].v;
        int lc = lca(ques[i].u,ques[i].v);//LCA单独处理
        rev(lc);
        ans[ques[i].id] = tmpans;
        rev(lc);
    }
    for(int i = 1;i <= ques_tot;i++)printf("%lld\n",ans[i]);
    return 0;
}