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

Orion545 · 2018-03-18 16:51:03 · 题解

备注

这篇题解提供了一种比较直观的莫队转移，不需要新建树之类的～

正文

树上？？？？？

别扯了，树又不是序列.....

这是我看到树上莫队的第一想法

但是，我们考虑在树上询问不同颜色的个数的问题，发现这么多询问下来，重复的依然很多，莫队的“消除重复”思想依然可以实现

而且谁说树上不能序列化了？dfs序听了这话想打人......

先考虑对子树的询问：一棵树，每个节点都有颜色，每次问你一个子树中有多少不同的颜色

我们发现一棵子树在dfs序上一定是连续的

那我们把dfs序求出来，再做标准莫队的过程就没问题了，甚至可以带上修改

但是，树上提问可不止子树询问，我们遇到的更多是树上两点之间的路径的询问

但是这种时候一条路径在dfs序上可就不是连续的了

难道我们树剖？常数卡死人......

不急，我们来推导一下怎么转移吧

我们考虑这样一个树，图示是树的一部分（也就是这两个询问涉及的部分）

我们当前处理出来的是询问(1,6)的答案，也就是这条黄色路径

我们下一个要求的是蓝色路径(2,4)的答案

这种情况下我们发现，其实每次增加的就是lca(1,2)到2，以及lca(4,6)到4的那些节点

同时lca(1,2)到1，以及lca(4,6)到6的路径上的节点要去掉

诶？

那岂不是可以求出两个lca，然后把这两对点路径上除了lca的点的状态都反过来就可以了？

别急这只是一种情况，但是这个结论，实际上是对的

我们说的多种情况，无非就是两个lca在树上的位置关系

而这一位置关系，实际上取决于两个询问的两端节点的lca的位置关系（有点绕，一定要看清楚）

而这个关系要么就是父亲-儿子，要么就是毫不相干

上面那种情况就是父亲-儿子，此时lca(1,2) and lca(4,6)中间的那些节点不会受到影响

而两个原lca如果相离的话，我们可以发现中间的那段节点被处理了两次，也就是反转再反转，实际上没有动

因此这个转移方式是合法的

还有一个问题：两条路径上的lca是否收到影响呢？

关于这一点，我们发现，lca(1,2)与lca(4.6)，在任何情况下都不应该被碰到，因此我们不能改变它们的状态

但是有一个点是需要注意的：就是新的询问两端的lca

这个点在前面的转移中会被反转掉，因此我们需要把它反转，统计答案，再转回去以免影响下一个询问

同样，这样做的时间效率，在每一块分sqrt(n)时，是在O(nsqrt(n))左右，带了修改也是O(n^(5/3))

这道题就是一个带修改的树上莫队模板咯

放一下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
inline ll read(){
    ll re=0,flag=1;char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re*flag;
}
struct edge{
    ll to,next;
}a[200010];
ll n,m,Q,first[100010],cntt,clk,block;
ll fa[100010],dep[100010],st[100010][20],dfn[100010];
ll v[100010],w[100010],x[100010];
inline void add(ll u,ll v){
    a[++cntt]=(edge){v,first[u]};first[u]=cntt;
    a[++cntt]=(edge){u,first[v]};first[v]=cntt;
}
void dfs(ll u,ll f){//dfs预处理dfn序
    ll i,v;
    fa[u]=st[u][0]=f;dep[u]=dep[f]+1;dfn[u]=++clk;
    for(i=first[u];~i;i=a[i].next){
        v=a[i].to;
        if(v==f) continue;
        dfs(v,u);
    }
}
void init(){
    for(ll i=1;i<=18;i++){
        for(ll j=1;j<=n;j++){
            st[j][i]=st[st[j][i-1]][i-1];
        }
    }
}
void _swap(ll &l,ll &r){l^=r;r^=l;l^=r;}
ll LCA(ll l,ll r){
    if(dep[l]>dep[r]) _swap(l,r);
    ll i;
    for(i=18;i>=0;i--) if(dep[st[r][i]]>=dep[l]) r=st[r][i];
    if(l==r) return l;
    for(i=18;i>=0;i--){
        if(st[l][i]!=st[r][i]){
            l=st[l][i];r=st[r][i];
        }
    }
    return fa[l];
}
ll curl,curr,curc,cntq,cntc,cnt[1000010];bool vis[100010];
ll ans[100010],tot;
struct query{//l,r就是询问的左右端点，c就是在第几次修改之后，i是它本来是第几个询问（输出用的）
    ll l,r,c,i;
}q[100010];
bool cmp(query l,query r){//自定义的排序
    if(dfn[l.l]/block!=dfn[r.l]/block) return dfn[l.l]/block<dfn[r.l]/block;
    else{
        if(dfn[l.r]/block!=dfn[r.r]/block) 
            return dfn[l.r]/block<dfn[r.r]/block;
        else return l.c<r.c;
    }
}
struct change{
    ll pos,to;
}c[100010];
void rev(ll i){//反转节点状态
    if(vis[i]) vis[i]=0,tot-=v[x[i]]*w[cnt[x[i]]],cnt[x[i]]--;
    else vis[i]=1,cnt[x[i]]++,tot+=v[x[i]]*w[cnt[x[i]]];
}
void change(ll i){
    if(!vis[c[i].pos]) _swap(c[i].to,x[c[i].pos]);
    else{
        rev(c[i].pos);
        _swap(c[i].to,x[c[i].pos]);
        rev(c[i].pos);
    }
}
int main(){
    memset(first,-1,sizeof(first));
    ll i,t1,t2,t3;
    n=read();m=read();Q=read();block=(ll)pow(n,0.60);
    for(i=1;i<=m;i++) v[i]=read(); 
    for(i=1;i<=n;i++) w[i]=read();
    for(i=1;i<n;i++){
        t1=read();t2=read();add(t1,t2);
    }
    for(i=1;i<=n;i++) x[i]=read();
    dfs(1,0);init();
    for(i=1;i<=Q;i++){
        t1=read();t2=read();t3=read();
        if(t1) q[++cntq].l=t2,q[cntq].r=t3,q[cntq].c=cntc,q[cntq].i=cntq;
        else c[++cntc].pos=t2,c[cntc].to=t3;
    }
    sort(q+1,q+cntq+1,cmp);

    //像常规莫队一样先把第一个节点处理了
    if(dfn[q[1].l]>dfn[q[1].r]) _swap(q[1].l,q[1].r);
    ll lca=LCA(q[1].l,q[1].r),l,r;curl=q[1].l;curr=q[1].r;
    l=curl;r=curr;
    while(l!=lca) rev(l),l=fa[l];
    while(r!=lca) rev(r),r=fa[r];
    while(curc<q[1].c) change(++curc);
    rev(lca);ans[q[1].i]=tot;rev(lca);

    for(i=2;i<=cntq;i++){
        if(dfn[q[i].l]>dfn[q[i].r]) _swap(q[i].l,q[i].r);
        lca=LCA(curr,q[i].r);l=curr;r=q[i].r;
        while(l!=lca) rev(l),l=fa[l];
        while(r!=lca) rev(r),r=fa[r];
        lca=LCA(curl,q[i].l);l=curl;r=q[i].l;
        while(l!=lca) rev(l),l=fa[l];
        while(r!=lca) rev(r),r=fa[r];
        while(curc>q[i].c) change(curc--);
        while(curc<q[i].c) change(++curc);
        lca=LCA(q[i].l,q[i].r);
        rev(lca);ans[q[i].i]=tot;rev(lca);//特殊处理lca
        curl=q[i].l;curr=q[i].r;
    }
    for(i=1;i<=cntq;i++) printf("%lld\n",ans[i]);
}

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

广告

备注

正文