CF893F Subtree Minimum Query 主席树trick

(Updated: )
(7 mins to read)

题意

给定一棵有点权的树，每次询问点u子树中距离u<=k的点的点权的最小值，要求在线回答

做法

询问子树，考虑dfs序，即询问$[in[u]：out[u]]$$[dep[u]：dep[u]+k]$中的min{a}二维偏序，发现每个dfs序对应了一个点，按照深度建主席树，每个版本的主席树维护的是$[1,dep[u]]$这个深度前缀中dfs序区间的最小值，按照bfs深度顺序更新。询问的时候只要ask dep[u]+k版本的主席树中[in[u], out[u]]区间的最小值即可

一些不一定对的思考：线段树可以高效维护一段区间的信息，而主席树可以维护各个版本的线段树，每个版本维护的是它及其之前的所有版本的前缀信息，所以主席树可以维护二维的信息，通过转变维度，巧妙的利用某一维来建树可以解决很多问题。该题中最小值不可减，所以只能询问前缀，而不能询问rt[l]-rt[r]，但是在该dfs序中的点dep[u]都是符合条件的，所以没有问题。再说带修的主席树，由于主席树维护的是每个版本的前缀信息，所以在修改的时候需要修改后面每个版本的信息，所以考虑在外层套一个树状数组，此时树状数组中每棵主席树维护的不再是前缀信息了，不需要继承前一个版本(rt[i]=rt[i-1])，每次的查询和询问操作都只与log棵主席树相关

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
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, r, a[N], in[N], out[N], dfn, dep[N];
int m, p, q, mxdep;
vector<int> G[N];
namespace PSegTree
{
  #define ls(x) t[x].l
  #define rs(x) t[x].r
  int rt[N], tot;
  struct node
  {
    int l, r, mn;
  }t[N<<5];
  inline void newnode(int &p)
  {
    t[++tot] = t[p];
    p = tot;
  }
  void upd(int &p, int l, int r, int x, int v)
  {
    newnode(p);
    if(l==r)
    {
      t[p].mn = min(t[p].mn, v);
      return;
    }
    int mid = (l+r) >> 1;
    if(x<=mid) upd(ls(p), l, mid, x, v);
    else upd(rs(p), mid+1, r, x, v);
    t[p].mn = min(t[ls(p)].mn, t[rs(p)].mn);
  }
  int ask(int p, int l, int r, int ql, int qr)
  {
    if(l>=ql&&r<=qr) return t[p].mn;
    int ans = INF, mid = (l+r)>>1;
    if(ql<=mid) ans = min(ans, ask(ls(p), l, mid, ql, qr));
    if(qr>mid) ans = min(ans, ask(rs(p), mid+1, r, ql, qr));
    return ans;
  }
  #undef ls
  #undef rs
}
using namespace PSegTree;
void dfs(int u, int fa)
{
  in[u] = ++dfn;
  dep[u] = dep[fa] + 1;
  mxdep = max(mxdep, dep[u]);
  for(int v : G[u])
  {
    if(v==fa) continue;
    dfs(v, u);
  }
  out[u] = dfn;
}
void bfs()
{
  queue<int> q;
  q.push(r);
  int curd = 0;
  rt[0] = 0;
  t[0].mn = INF;
  while(sz(q))
  {
    int u = q.front(); q.pop();
    if(dep[u]>curd)
    {
      rt[dep[u]] = rt[curd];
      curd = dep[u];
    }
    upd(rt[dep[u]], 1, n, in[u], a[u]);
    for(int v : G[u])
      if(dep[v]==dep[u]+1) q.push(v);
  }
}
int main()
{
  scanf("%d%d", &n, &r);
  for(int i=1; i<=n; i++) scanf("%d", a+i);
  for(int i=1; i<n; i++)
  {
    int x, y; scanf("%d%d", &x, &y);
    G[x].pb(y); G[y].pb(x);
  }
  dfs(r, 0);
  bfs();
  scanf("%d", &m);
  int lstans = 0;
  while(m--)
  {
    scanf("%d%d", &p, &q);
    p = (p+lstans)%n + 1;
    q = (q+lstans)%n;
    printf("%d\n", lstans=ask(rt[min(mxdep, dep[p]+q)], 1, n, in[p], out[p]));
  }
  return 0;
}