【题目大意】
给出一棵树与每个结点的温度，q次询问，每次给定选定一个结点与一个范围，判断有多少个结点被感染
一个结点被感染仅当相邻结点被感染，自己的温度在给定的范围内，如果一开始给定的结点都不在这个温度范围内，则没有结点被感染
【思路】
题目给出了一个重点，离根结点的结点温度越低，我们对于每次询问可以先找到温度小于r的最高的那个结点，这里采用树上倍增求LCA的方式求的温度最高的那个结点，我们就将问题转换成为了找出当前结点的子树中有多少结点的温度大于等于l，
我们用dfs序的方式将子树问题转换为区间问题，然后再用线段去维护某一区间温度大于l的数量
【代码】
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e6+7;
vector<ll>e[maxn];
ll in[maxn];//时间戳——进
ll out[maxn];//时间戳——出
ll num[maxn];
ll fa[maxn][30];//代表第i个结点的2^(j-1)个父亲
ll t[maxn]; //温度
ll dep[maxn];//树的深度
ll lg[maxn];
ll tim=0;
ll n;
typedef struct node//保存询问结点
{
ll i,l,x;
bool operator < (const node & y)const
{
return l<y.l;
}
}node;
struct tree //线段树
{
ll l,r,sum;
}tree[maxn*4];
void build(ll rt,ll l,ll r)
{
tree[rt].l=l;
tree[rt].r=r;
tree[rt].sum=r-l+1;
if(l!=r)
{
ll mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
}
void change(ll rt,ll x)
{
tree[rt].sum--;
if(tree[rt].l!=tree[rt].r)
{
ll mid=(tree[rt].l+tree[rt].r)>>1;
if(x<=mid)
{
change(rt<<1,x);
}
else change(rt<<1|1,x);
}
}
ll ask(ll rt,ll l,ll r)
{
if(tree[rt].l>=l&&tree[rt].r<=r)
{
return tree[rt].sum;
}
ll mid=(tree[rt].l+tree[rt].r)>>1;
ll ans=0;
if(l<=mid)
{
ans+=ask(rt<<1,l,r);
}
if(r>mid) ans+=ask(rt<<1|1,l,r);
return ans;
}
//------------------end
vector<node>ak;
ll ans[maxn];
void dfs1(ll x,ll f)//求dfs序列，将树节点转换为线性区间
{
in[x]=(++tim); //进
num[tim]=x;
for(ll i=0;i<e[x].size();i++)
{
ll v=e[x][i];
if(v!=f)
{
dfs1(v,x);
}
}
out[x]=tim; // 出
}
void dfs2(ll x)//书上倍增求父亲
{
for(ll i=1;i<=lg[dep[x]];i++)
{
if(fa[x][i-1])
{
fa[x][i]=fa[fa[x][i-1]][i-1];
}
else break;
}
for(ll i=0;i<e[x].size();i++)
{
ll v=e[x][i];
if(v!=fa[x][0])
{
fa[v][0]=x;
dep[v]=dep[x]+1;
dfs2(v);
}
}
}
ll lca(ll x,ll r)// 最近公共祖先求最高的小于r的结点
{
ll y=x;
for(ll i=lg[dep[x]];i>=0;i--)
{
if(t[fa[y][i]]<=r)
{
y=fa[y][i];
}
}
return y;
}
bool cmp(ll a,ll b)
{
return t[a]<t[b];
}
int main()
{
deque<ll>Q;
scanf("%lld",&n);
for (int i = 1; i <= n; i++)
lg[i] = lg[i - 1] + (1<<lg[i - 1] == i);
t[0]=0x3f3f3f3f;
for(ll i=1;i<=n-1;i++)
{
ll u,v;
scanf("%lld%lld",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
for(ll i=1;i<=n;i++)
{
scanf("%lld",&t[i]);
Q.push_back(i);
}
sort(Q.begin(),Q.end(),cmp);
dfs1(1,0);
dfs2(1);
ll q;
scanf("%lld",&q);
for(ll i=1;i<=q;i++){
node tmp;
tmp.i=i;
ll x,l,r;
scanf("%lld%lld%lld",&x,&l,&r);
if(t[x]<l||t[x]>r)
{
tmp.l=-1;
}
else
{
ll y=lca(x,r);//求出最高的结点
tmp.x=y;
tmp.l=l;
//利用树状数组维护dfs序
}
ak.push_back(tmp);
}
build(1,1,n);
sort(ak.begin(),ak.end());
for(ll i=0;i<ak.size();i++)
{
node tmp=ak[i];
if(tmp.l==-1)
{
ans[ak[i].i]=0;
}
else
{
while(!Q.empty()&&t[Q[0]]<ak[i].l)
{
change(1,in[Q[0]]);
Q.pop_front();
}
// cout<<in[ak[i].x]<<" "<<out[ak[i].x]<<endl;
ans[ak[i].i]=ask(1,in[ak[i].x],out[ak[i].x]);
}
}
for(ll i=1;i<=q;i++)
{
cout<<ans[i]<<endl;
}
return 0;
}
/*
11
1 9
1 10
1 5
1 4
9 2
9 7
9 6
4 8
3 7
7 11
399 289 285 390 396 287 288 286 398 397 280
*/