题目大意

一个国家有个城市，由个道路彼此相连，构成一个树。其中首都（一号节点）紧挨着 艾 雅 法 拉 火山，所以温度最高，其它城市的温度是随着距离首都的距离而递减的（每条道路长度可以认为是相同的）。现在一种病毒在城市​爆发，它的可以存活的温度区间是​​。当有道路相连的两个城市温度都可以让病毒存活，且其中一个城市已经被病毒感染，那么病毒就会传播到另一个城市。

给定每个城市的温度和条道路，需要回答次询问：假如有存活温度范围为的病毒在第个城市爆发，那么病毒会传染几个城市？

思路

这个题目的思路很好想，就是实现需要一些较难的知识点，主 席 树。（dalao请忽略）

  • 病毒在城市爆发，那么就向上找到它最高能传染的城市，假设为。
  • 求在以为根的子树上有多少城市的温度大于​。

第一步可以用倍增等方法在的时间内求得，而第二步就可能困难了，需要用到主席树。

那么主席树是如何和树上统计联系起来呢？

我们知道，可持久化线段树是可以保留历史版本的线段树了

而利用离散化+可持续化权值线段树 可以实现 查询给定序列某个区间的第k大。（这部分不懂的可以去学习一下）

那么怎么用主席树去实现在树上的查询呢？

首先，我们从号节点对整个树进行一次dfs，并给每一个节点一个时间戳，那么dfs完之后，每个节点和它的子节点的时间戳，刚好构成了一个连续的序列。既然有了连续的序列，那么它们的权值就可以通过主席树来维护了。即我们按照时间戳来把每个点的权值排成一个序列，然后用主席树去维护。

那么在树上维护的操作已经解决，那么该如何利用它去解决**求在以为根的子树上有多少城市的温度大于​​?**

我们不妨使用二分法，我们假设有个城市可以被传染，然后查询的子树上第大的城市温度，让它与作比较。那么单次查询的时间复杂度就是。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int maxN = 1e5 + 7;

int n, m, tot;
ll ls[maxN << 5], rs[maxN << 5], rt[maxN << 5], sum[maxN << 5], a[maxN], ind[maxN], rangeLeft[maxN], rangeRight[maxN];
int head[maxN], edgeNum, len, fa[21][maxN], pos;

struct Edge {
    int from, to;
}e[maxN << 1];

inline void add(int u, int v)
{
    e[++edgeNum].from = head[u];
    e[edgeNum].to = v;
    head[u] = edgeNum;
}

int built(int l, int r)
{
    int root = ++tot;
    if(l == r)
        return tot;
    int mid = (l + r) >> 1;
    ls[root] = built(l, mid);
    rs[root] = built(mid + 1, r);
    return root;
}

ll update(ll k, ll l, ll r, ll root) //往主席树中插入新的节点
{
    ll dir = ++tot;
    ls[dir] = ls[root]; rs[dir] = rs[root]; sum[dir] = sum[root] + 1;
    if(l == r)
        return dir;
    ll mid = (l + r) >> 1;
    if(k <= mid)
        ls[dir] = update(k, l, mid, ls[dir]);
    else
        rs[dir] = update(k, mid + 1, r, rs[dir]);
    return dir;
}

ll query(ll u, ll v, ll l , ll r, ll k) //询问区间[u,v]中的第k大的数
{
    ll mid = (l + r) >> 1, x = sum[ls[v]] - sum[ls[u]];
    if(l == r)
        return l;
    if(k <= x)
        return query(ls[u], ls[v], l, mid, k);
    else
        return query(rs[u], rs[v], mid + 1, r, k - x);

}

inline int getId(const ll& val) //离散化
{
    return lower_bound(ind + 1, ind + len + 1, val) - ind;
}

void dfs(ll x) // 确定时间戳，顺便初始化倍增数组的第一层
{
    ++pos;
    rt[pos] = update(getId(a[x]), 1, len, rt[pos - 1]); //按照dfs序，往主席树中插入（离散化后的数）
    rangeLeft[x] = pos;//记录每个点的子树时间戳区间。
    for(int i = head[x]; i; i = e[i].from) {
        int y = e[i].to;
        if(y != fa[0][x]) {
            fa[0][y] = x;
            dfs(y);
        }
    }
    rangeRight[x] = pos;//记录每个点的子树时间戳区间。
    return ;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        add(x, y); add(y, x);
    }
    for(int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        ind[i] = a[i];
    }
    sort(ind + 1, ind + 1 + n);//离散化
    len = unique(ind + 1, ind + 1 +n) - ind - 1;
    rt[0] = built(1, len); //建立初始线段树
    dfs(1);
    for(int i = 1; i <= 20; ++i)
        for(int j = 1; j <= n; ++j)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
    scanf("%d", &m);
    while(m--) {
        ll x, l, r;
        scanf("%lld%lld%lld", &x, &l, &r);
        if(a[x] < l || a[x] > r) {
            printf("0\n");
            continue;
        }//开始传播的城市温度就不适宜。
        for(int i = 20; i >= 0; i--)
            if(fa[i][x] && a[fa[i][x]] <= r)
                x = fa[i][x]; //向上找到能传播的最高城市
        l = getId(l); r = getId(r);
        ll qm = rangeRight[x] - rangeLeft[x] + 1, ql = 1, qr = qm, ans = 0;
        while(ql <= qr) { //qm为这个子树有多少个子节点
            ll mid = (ql + qr) >> 1;
            ll p = query(rt[rangeLeft[x] - 1], rt[rangeRight[x]], 1, len, mid);
            if(p >= l) { //我们需要二分到 温度第mid大的城市时，这个城市温度就是最小且适宜的城市。
                qr = mid - 1;
                ans = mid;
            }
            else
                ql = mid + 1;
        }
        ans = qm - ans + 1; //用总子树数量减去温度最小且适宜的城市的序号（这个序号是按温度大小排列的）
        printf("%lld\n", ans);//就得出了能够传染的城市数量了。
    }
    return 0;
}