Eyjafjalla (2021牛客多校第九场E)

赛中一直没有想明白，怎么向上查询到其他子树的满足条件数，于是一直在乱调
其实，只需要向上倍增到满足符合的节点，然后从这个节点开始查询。
大家伙好像用主席树用的比较多，（主席树还不太会...呜呜），这边讲一下线段树的做法
首先，数显剖分将这颗树映射到数组中，简单的两个dfs，同时记录每个节点的前置节点，倍增的思想，其实我刚刚才学会，之前LCA都是用树链的，有机会多找人家问问。

void dfs1(int u,int pre){
    Size[u] = 1;
    fa[u][0]=pre;
    for(int i=1;i<20;i++) fa[u][i] = fa[fa[u][i-1]][i-1];
    /*fa用来倍增出这个节点的父亲，父亲的父亲......*/ 
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(!Size[v]){
            dfs1(v,u);
            Size[u]+=Size[v];
            if(Size[son[u]]<Size[v]){
                son[u]=v;  //树链剖分，重儿子 
            }
        }
    }
}
void dfs2(int u,int tp){
    top[u]=tp;
    dfn[++cnt]=u;  //dfs序 
    pos[u]=cnt;  //表示这个节点在数组中的位置 
    if(son[u]) dfs2(son[u],tp);  //优先走重儿子 
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(!top[v]) dfs2(v,v);
    }
}

之后，我们根据每个节点的温度，建一颗线段树，Max[],Min[]数组用来维护这个区间的最大温度和最低温度，pushup写法也很简单，同时不需要update。

void pushup(int rt){
    Max[rt] = max(Max[rt<<1],Max[rt<<1|1]);
    Min[rt] = min(Min[rt<<1],Min[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        Max[rt] = a[l];
        Min[rt] = a[l];
        return ;
    }
    int m = (l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}

然后我们看查询操作，因为题目给的发源点x的温度可能在[l,r]之间，直接从x点查询会非常非常的麻烦，比赛的时候就一直卡在这个地方，想着怎么分段。之后听何巨巨的做法，要向上找到一个节点，保证这个节点的再上一个节点的温度会大于r，我们把这个节点当作起始点，因为这时候就可以保证子树所有的节点温度都低于r，题目就转化为：
从这个节点开始的子树，有多少个节点的温度在给定的温度范围内。
有因为我们已经述链剖分将树中的节点映射到数组中，所以我们要查询的范围就是[pos[x],pos[x]+Size[x]-1]，其中x就是我们向上倍增找到的节点，pos表示这个节点在映射数组中的位置，Size表示以这个节点为根的子树大小。

int query(int L,int R,int l,int r,int rt,int t1,int t2){
    //L、R代表查询的区间，l、r表示当前所在区间，rt当前所在节点，t1是最高温度，t2是最低温度 
    int ans = 0;
    if(L<=l&&r<=R){   //如果当前所在节点在我们要查询的区间中 
        int m = (l+r)>>1;
        if(Min[rt]>=t2) {   //这个区间的最低温度高于最低温度就满足 
            ans+=r-l+1;    //返回这个区间的节点数 
            return ans;
        }
        if(Max[rt]<t2){   //如果这个区间的最高温比t2还小，就不满足，返回0； 
            return 0;
        }
    }    
    int m = (l+r)>>1;
    if(L<=m) ans+=query(L,R,l,m,rt<<1,t1,t2);
    if(R> m) ans+=query(L,R,m+1,r,rt<<1|1,t1,t2);
    return ans;
}

最后贴下代码，最好还是自己调调

#include<bits/stdc++.h>
#define sc(a) scanf("%d",&a)
using namespace std;
typedef long long ll;
const int maxn= 4e5+5;
ll a[maxn],n;
vector<int> G[maxn];
int son[maxn],Size[maxn],fa[maxn][21],top[maxn],pos[maxn],cnt,dfn[maxn];
int Min[maxn],Max[maxn];
void dfs1(int u,int pre){
    Size[u] = 1;
    fa[u][0]=pre;
    for(int i=1;i<20;i++) fa[u][i] = fa[fa[u][i-1]][i-1];
    /*fa用来倍增出这个节点的父亲，父亲的父亲......*/ 
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(!Size[v]){
            dfs1(v,u);
            Size[u]+=Size[v];
            if(Size[son[u]]<Size[v]){
                son[u]=v;  //树链剖分，重儿子 
            }
        }
    }
}
void dfs2(int u,int tp){
    top[u]=tp;
    dfn[++cnt]=u;  //dfs序 
    pos[u]=cnt;  //表示这个节点在数组中的位置 
    if(son[u]) dfs2(son[u],tp);  //优先走重儿子 
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(!top[v]) dfs2(v,v);
    }
}
void pushup(int rt){
    Max[rt] = max(Max[rt<<1],Max[rt<<1|1]);
    Min[rt] = min(Min[rt<<1],Min[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        Max[rt] = a[l];
        Min[rt] = a[l];
        return ;
    }
    int m = (l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt,int t1,int t2){
    //L、R代表查询的区间，l、r表示当前所在区间，rt当前所在节点，t1是最高温度，t2是最低温度 
    int ans = 0;
    if(L<=l&&r<=R){   //如果当前所在节点在我们要查询的区间中 
        int m = (l+r)>>1;
        if(Min[rt]>=t2) {   //这个区间的最低温度高于最低温度就满足 
            ans+=r-l+1;    //返回这个区间的节点数 
            return ans;
        }
        if(Max[rt]<t2){   //如果这个区间的最高温比t2还小，就不满足，返回0； 
            return 0;
        }
    }    
    int m = (l+r)>>1;
    if(L<=m) ans+=query(L,R,l,m,rt<<1,t1,t2);
    if(R> m) ans+=query(L,R,m+1,r,rt<<1|1,t1,t2);
    return ans;
}
void solve(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int cnt = 0;
    dfs1(1,1),dfs2(1,1);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%lld",&x);
        a[pos[i]]= x;
    }
    build(1,n,1);
    int Q;
    cin>>Q;
    for(int i=1;i<=Q;i++){
        int x,t2,t1;
        scanf("%d%d%d",&x,&t2,&t1);
        if(a[pos[x]]<t2||a[pos[x]]>t1){
            cout<<0<<'\n';
        }
        else{
            for(int i=19;i>=0;i--){
                if(a[pos[fa[x][i]]]>t1) continue;
                x = fa[x][i];
            }
            int ans = query(pos[x],pos[x]+Size[x]-1,1,n,1,t1,t2);
            cout<<ans<<'\n';
        }
    }
    return ;
}
int main()
{
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

现在越发感觉自己好多东西不会了，这题赛中可以出的。