【牛客竞赛】Eyjafjalla题解

题目大意

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

给定每个城市的温度 $a_i$ 和 $n-1$ 条道路，需要回答 $m$ 次询问：假如有存活温度范围为 $[l, r]$ 的病毒在第 $i$ 个城市爆发，那么病毒会传染几个城市？

题目链接

思路

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

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

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

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

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

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

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

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

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

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

代码

#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)
{
    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]);
    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) {
            ll mid = (ql + qr) >> 1;
            ll p = query(rt[rangeLeft[x] - 1], rt[rangeRight[x]], 1, len, mid);
            if(p >= l) {
                qr = mid - 1;
                ans = mid;
            }
            else
                ql = mid + 1;
        }
        ans = qm - ans + 1;
        printf("%lld\n", ans);
    }
    return 0;
}