Fork me on GitHub

Eyjafjalla

字数统计: 1.5k字   |   阅读时长≈ 6分

题目大意

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

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

题目链接

思路

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

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

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

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

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

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

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

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#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;
}

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true


   退役OIer，现役ACMer，人工智能专业的苦逼大学牲

   会记录一些ACM/OI中的一些算法和题目，以及一些在学校上的课的内容，比如AI之类的

  和一些自己感兴趣的东西。
  感谢访问