题解 | #Eyjafjalla#

Eyjafjalla

https://ac.nowcoder.com/acm/contest/11260/E

Emm...

照着标答写的码，再详细捋一遍

题目大意：

给了一个以 1 为根的有根树，儿子的权值小于父亲的权值。

多次询问，病毒在 $x$ 节点爆发，可以向任何权值范围在 $图片说明$ 的节点传播，求最多扩散了多少个节点。

整体思路：

1、先让病毒向上传播到 $y$ 节点，满足 $y$ 节点的父节点权值 $>r$ 。（这样可以确保病毒只会在以 $y$ 为根的子树上传播）
2、然后求以 $图片说明$ 为根的子树上，有多少节点权值 $图片说明$ $图片说明$

操作过程：

（在线做法）
0、前向星存图，权值离散化

void add(ll u,ll v,ll w){
    eg[++cnt].to=v;
    eg[cnt].nxt=head[u];
    eg[cnt].w=w;
    head[u]=cnt;
}

void dcre(){//离散
    num=n;
    sort(c+1,c+num+1);
    num=unique(c+1,c+num+1)-c-1;
    L(i,1,n){
        a[i]=lower_bound(c+1,c+num+1,a[i])-c;
    }
}

1、利用dfs序建立主席树，初始化倍增数组

void bd_tree(ll l,ll r,ll pre,ll &now,ll val){
    trs[++cnt]=trs[pre];
    now=cnt;
    trs[now].sum++;
    if(l==r)return;
    ll mid=(l+r)/2;
    if(val<=mid){
        bd_tree(l,mid,trs[pre].l,trs[now].l,val);
    }
    else{
        bd_tree(mid+1,r,trs[pre].r,trs[now].r,val);
    }
}

void dfs(ll x){
    ll pre=root[pos++];
    bd_tree(1,n,pre,root[pos],a[x]);//建主席树
    q[x].l=pos;//dfs序 
    for(ll i=head[x];i;i=eg[i].nxt){
        if(eg[i].to!=fat[0][x]){
            fat[0][eg[i].to]=x;//构建1代祖先关系 
            dfs(eg[i].to);
        }
    }
    q[x].r=pos;
}

void init(){
    pos=0;cnt=0;
    trs[0]={0,0,0};
    fat[0][1]=0;
    dfs(1);

    L(i,1,20)//构建2^i代祖先关系 
        L(j,1,n)
            fat[i][j]=fat[i-1][fat[i-1][j]];
    return;
}

2、利用倍增法求 $y$ 节点

   R(i,20,0){
        if(fat[i][x]&&a[fat[i][x]]<=r)x=fat[i][x];
   }

3、查询以 $y$ 节点为根的子树上权值 $图片说明$ $图片说明$ 的个数

ll query(ll l,ll r,ll pl,ll pr,ll val){
    if(l==r)return trs[pr].sum-trs[pl].sum;
    ll mid=(l+r)/2;
    if(val<=mid){//val在左子树中，所以右子树全部满足权值>=l
        return query(l,mid,trs[pl].l,trs[pr].l,val)+trs[trs[pr].r].sum-trs[trs[pl].r].sum;
    }
    else{
        return query(mid+1,r,trs[pl].r,trs[pr].r,val);
    }
}
/*--主函数中--*/
ans=query(1,n,root[q[x].l-1],root[q[x].r],l);
/*----------*/

4、最后

printf("%lld\n",ans);

完整代码：

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e5+10,maxn=3e3+10,mod=1e9+7;
using namespace std;
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}

ll m,n,x,y,z,t,k,l,r,p,pp,nx,ny,num,sum,pos,tot,block,key,cnt,flag,minn,maxx,ans;
ll a[N],c[N],head[N],root[N],fat[21][N];

struct qq{ll l,r;}q[N];
struct tree{ll l,r,sum;}trs[20*N];
struct edge{ll to,nxt,w;}eg[N*2];

bool cmp(qq u,qq v){
    if(u.l!=v.l)return u.l<v.l;
    else return u.r<v.r;
}
bool cmp1(ll u,ll v){return u>v;}
struct cmps{bool operator()(qq u,qq v){
    return (u.l>v.l);
}};//升序

void add(ll u,ll v,ll w){
    eg[++cnt].to=v;
    eg[cnt].nxt=head[u];
    eg[cnt].w=w;
    head[u]=cnt;
}

void dcre(){//离散
    num=n;
    sort(c+1,c+num+1);
    num=unique(c+1,c+num+1)-c-1;
    L(i,1,n){
        a[i]=lower_bound(c+1,c+num+1,a[i])-c;
    }
}

void bd_tree(ll l,ll r,ll pre,ll &now,ll val){
    trs[++cnt]=trs[pre];
    now=cnt;
    trs[now].sum++;
    if(l==r)return;
    ll mid=(l+r)/2;
    if(val<=mid){
        bd_tree(l,mid,trs[pre].l,trs[now].l,val);
    }
    else{
        bd_tree(mid+1,r,trs[pre].r,trs[now].r,val);
    }
}

ll query(ll l,ll r,ll pl,ll pr,ll val){
    if(l==r)return trs[pr].sum-trs[pl].sum;
    ll mid=(l+r)/2;
    if(val<=mid){//val在左子树中，所以右子树全部满足权值>=l
        return query(l,mid,trs[pl].l,trs[pr].l,val)+trs[trs[pr].r].sum-trs[trs[pl].r].sum;
    }
    else{
        return query(mid+1,r,trs[pl].r,trs[pr].r,val);
    }
}

void dfs(ll x){
    ll pre=root[pos++];
    bd_tree(1,n,pre,root[pos],a[x]);//建主席树
    q[x].l=pos;//dfs序 
    for(ll i=head[x];i;i=eg[i].nxt){
        if(eg[i].to!=fat[0][x]){
            fat[0][eg[i].to]=x;//构建1代祖先关系 
            dfs(eg[i].to);
        }
    }
    q[x].r=pos;
}

void init(){
    pos=0;cnt=0;
    trs[0]={0,0,0};
    fat[0][1]=0;
    dfs(1);

    L(i,1,20)//构建2^i代祖先关系 
        L(j,1,n)
            fat[i][j]=fat[i-1][fat[i-1][j]];
}

int main(){
    scanf("%lld",&n);
    L(i,1,n-1){
        scanf("%lld%lld",&x,&y);
        add(x,y,0);
        add(y,x,0);
    }
    L(i,1,n){
        scanf("%lld",&a[i]);c[i]=a[i];
    }
    dcre();
    init();

    scanf("%lld",&m);
    while(m--){
        scanf("%lld%lld%lld",&x,&l,&r);
        l=lower_bound(c+1,c+num+1,l)-c;
        r=upper_bound(c+1,c+num+1,r)-c-1;
        if(a[x]<l||a[x]>r){
            printf("0\n");continue;
        }
        R(i,20,0){
            if(fat[i][x]&&a[fat[i][x]]<=r)x=fat[i][x];
        }
        ans=query(1,n,root[q[x].l-1],root[q[x].r],l);
        printf("%lld\n",ans);

    }
}

感想：

· Ahhhh...
· 好庞大、好宏伟、好美妙的码
· 总算码完了
· 说起来这是我码的第二颗主席树（主席树也是做到这道题后在去学的QAQ），一开始第三步求的时候过于僵硬，用二分查找答案，然后套“区间第K大”那道主席树模板的码(T-T)……后来重新看了权值线段树后改简洁了，直接查询即可。
· 码的时候一边感慨主席树的妙，一边僵硬的Debug，内心既崩溃又欣喜…抓耳挠腮了半天…
· 不过好在半天下来终于AC过了
· 后续可以再去学学离线树状数组和线段树合并的做法

· 最后的最后，本人小菜鸡一枚，欢迎各位批评指正~