题解 P2137 【Gty的妹子树】

· · 题解

分析：

都说这道提的经典做法之一是树分块，但为什么没人写这个做法的题解呢？

块状树与树链剖分的思想有些类似，都是将树进行适当的划分。块状树借用了分块的思想，通过把一个树分成若干块以实现更快的树上查询和修改。

我们可以通过一遍dfs实现对树的分块，具体方法是：令根节点所在块为第0块，然后向下dfs，如果一个节点的父亲节点所在块的大小小于你预设的SIZE（块的大小），那么就可以让这个节点与其父节点在同一块中，如果一个节点的父亲节点所在块的大小等于你预设的SIZE，那么对于这个节点，我们可以新建一个块。

对于每一个块，我们可以用一个vector维护这个块内节点的权值，并维护起有序性，即保证vector内元素单调不降（原因稍后会提到），维护方法类似于冒泡排序。

对于查询操作，我们可以通过从子树根节点dfs实现，类似散块暴力，整块维护的思想（注意这里要实现两个dfs函数dfsans()和dfsblock()，分别对应散块的查询和整块的查询）。整块的查询，我们可通过upper_bound()二分实现，这也是为什么要保证vector内元素单调不降。

对于修改操作，我们可以直接维护vector，然后更改w[u]即可（注意顺序）。

对于插入操作，类似于一开始dfs对树分块时的方法，根据父亲节点所在块的大小决定是否新建块。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
struct ios{
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
}io;
const int MAXN=60005;
const int SIZE=305;
int n,m,w[MAXN],head[MAXN],bhead[MAXN],ecnt,becnt,tot,fa[MAXN],belong[MAXN];
struct Edge{
    int to,nxt;
}e[MAXN<<1];
struct BlockEdge{
    int to,nxt;
}be[MAXN<<1];
struct Block{
    vector<int> a;
    Block(){
        a.clear();
    }
    inline void ins(int x){
        a.push_back(x);
        for(int i=a.size()-1;i;i--)
            if(a[i-1]>a[i]) swap(a[i-1],a[i]);
            else break;
    }
    inline void upd(int x,int k){
        int pos=lower_bound(a.begin(),a.end(),x)-a.begin();
        a[pos]=k;
        for(int i=pos;i;i--)
            if(a[i-1]>a[i]) swap(a[i-1],a[i]);
            else break;
        for(int i=pos;i<a.size()-1;i++)
            if(a[i]>a[i+1]) swap(a[i],a[i+1]);
            else break;
    }
    inline int query(int x){
        return a.end()-upper_bound(a.begin(),a.end(),x);
    }
}bl[MAXN];
inline void add_edge(int bg,int ed){
    ecnt++;
    e[ecnt].to=ed;
    e[ecnt].nxt=head[bg];
    head[bg]=ecnt;
}
inline void add_blockedge(int bg,int ed){
    becnt++;
    be[becnt].to=ed;
    be[becnt].nxt=bhead[bg];
    bhead[bg]=becnt;
}
void dfs(int x,int pre){
    fa[x]=pre;
    if(bl[belong[pre]].a.size()==SIZE){
        belong[x]=++tot;
        bl[tot].ins(w[x]);
        add_blockedge(belong[pre],tot);
    }
    else{
        belong[x]=belong[pre];
        bl[belong[x]].ins(w[x]);
    }
    for(int i=head[x];i;i=e[i].nxt){
        int ver=e[i].to;
        if(ver==pre) continue;
        dfs(ver,x);
    }
}
int dfsblock(int x,int k){
    int ans=bl[x].query(k);
    for(int i=bhead[x];i;i=be[i].nxt){
        int ver=be[i].to;
        ans+=dfsblock(ver,k);
    }
    return ans;
}
int dfsans(int x,int k){
    int ans=(w[x]>k?1:0);
    for(int i=head[x];i;i=e[i].nxt){
        int ver=e[i].to;
        if(ver==fa[x]) continue;
        if(belong[ver]==belong[x]) ans+=dfsans(ver,k);
        else ans+=dfsblock(belong[ver],k);
    }
    return ans;
}
int main(){
    io>>n;
    for(int i=1;i<n;i++){
        int u,v;io>>u>>v;
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1;i<=n;i++)
        io>>w[i];
    dfs(1,0);
    io>>m;
    int lastans=0;
    while(m--){
        int opt,u,x;
        io>>opt>>u>>x;
        u^=lastans,x^=lastans;
        if(opt==0){
            lastans=dfsans(u,x);
            printf("%d\n",lastans);
        }
        else if(opt==1){
            bl[belong[u]].upd(w[u],x);
            w[u]=x;
        }
        else{
            w[++n]=x;
            add_edge(u,n);
            fa[n]=u;
            if(bl[belong[u]].a.size()==SIZE){
                belong[n]=++tot;
                bl[tot].ins(w[n]);
                add_blockedge(belong[u],tot);
            }
            else{
                belong[n]=belong[u];
                bl[belong[n]].ins(w[n]);
            }
        }
    }
    return 0;
}

我为了卡常写了fread()......