Eyjafjalla

= =两个月不学习的fw这两个月来写的第一个题..
简单的来说就是树状数组硬搞...
首先在假如温度区间不在这个范围的点,先做个标记,就不用往上跳,且下面的点也一定不行..
然后就简单的倍增因为符合单调性就跳,跳到最高点然后判断子树中合法的.
简单的说就是在这个温度区间的,然后因为不涉及修改操作,可以树状数组离线按权值排序,左右端点的权值先分开再整合..然后离散化一下dfs序一下就可以通过这个题目了.\

code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=20;
vector<int>G[N<<2];
int ls[N<<2],id,t[N<<2],x[N<<2],L[N<<2],R[N<<2],c[N<<2],n,num;
int bit(int u)
{
    return u&(-u);
}

void add(int u)
{
    while(u<=num)
    {
        c[u]++;
        u+=bit(u);
    }
}

int qry(int u)
{
    int res=0;
    while(u)
    {
        res+=c[u];
        u-=bit(u);
    }
    return res;
}

int f[N][M],sz[N],idx,S[N];

struct Qry{
    int l,r,wl,wr,id;
}Q[N];

struct cs{
    int w,id;
}a[N];

bool cnp(cs A,cs B)
{
    return A.w<B.w;
}

bool Ans(Qry A,Qry B)
{
    return A.id<B.id;
}

struct Res{
    int w,l,r,id,op,ans,f;
}ask[N<<2];

bool cmmp(Res A,Res B)
{
    return A.w<B.w;
}

bool cnnp(Res A,Res B)
{
    if(A.id==B.id)  return A.op>B.op;
    else            return A.id<B.id;
}

void init(int u,int fa)
{
    f[u][0]=fa;sz[u]=1;S[u]=++idx;
    for(int i=1;i<=19;i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int v:G[u])
    {
        if(v==fa)   continue;
        init(v,u);
        sz[u]+=sz[v];
    }
}

int main()
{
    scanf("%d",&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);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t[i]);
        ls[++id]=t[i];
    }
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&x[i],&L[i],&R[i]);
        ls[++id]=L[i];
        ls[++id]=R[i];
    }
    sort(ls+1,ls+1+id);
    num=unique(ls+1,ls+1+id)-ls-1;
    for(int i=1;i<=n;i++)
    {
        t[i]=lower_bound(ls+1,ls+1+num,t[i])-ls;
        a[i].w=t[i];
        a[i].id=i;
    }
    for(int i=1;i<=q;i++)
    {
        L[i]=lower_bound(ls+1,ls+1+num,L[i])-ls;
        R[i]=lower_bound(ls+1,ls+1+num,R[i])-ls;
    }
    t[0]=1e9;
    init(1,0);
    int dd=0;
    for(int i=1;i<=q;i++)
    {
        bool fl=false;
        //找到每个点的节点在哪.
        int u=x[i];
        Q[i].id=i;
        Q[i].wl=L[i];
        Q[i].wr=R[i];
        if(t[u]>R[i]||t[u]<L[i])    fl=true;
        for(int j=19;j>=0;j--)
        {
            if(t[f[u][j]]<=R[i])    u=f[u][j];
        }
        Q[i].l=S[u];
        Q[i].r=S[u]+sz[u]-1;
        ask[++dd].id=i;
        ask[dd].op=0;
        ask[dd].l=Q[i].l;
        ask[dd].r=Q[i].r;
        ask[dd].w=L[i]-1;
        if(fl)  ask[dd].f=1;
        else    ask[dd].f=0;
        ask[++dd].id=i;
        ask[dd].op=1;
        ask[dd].l=Q[i].l;
        ask[dd].r=Q[i].r;
        ask[dd].w=R[i];
        if(fl)  ask[dd].f=1;
        else    ask[dd].f=0;
    }
    sort(a+1,a+1+n,cnp);
    sort(ask+1,ask+1+dd,cmmp);
    int l=1;
    for(int i=1;i<=dd;i++)
    {
        while(l<=n&&a[l].w<=ask[i].w)    add(S[a[l].id]),l++;
        if(ask[i].f)     ask[i].ans=0;
        else             ask[i].ans=qry(ask[i].r)-qry(ask[i].l-1);
    }
    sort(ask+1,ask+1+dd,cnnp);
    for(int i=1;i<=dd;i+=2)
    {
        printf("%d\n",ask[i].ans-ask[i+1].ans);
    }
    return 0;
}