CF1110F Nearest Leaf

题解
dfs序, 线段树

Description

给你一颗满足编号 = dfs 序的带边权的有根树。$m$ 次询问，每次给出 $v,l,r$ 求编号在 $[l,r]$ 中的叶子到 $v$ 节点的最短距离

$n,m \leq 5\times10^5,w \leq 10^9$

Solution

如果我们知道 $u$ 节点到所有叶子的最短路，如何求出他的某一个儿子 $v$ 到所有叶子的最短路呢？

不妨设 $(u,v)$ 的边权是 $w$ 。那么在 $v$ 这颗子树内的叶子到 $v$ 的距离较 $u$ 要减少 $w$ ； $v$ 这颗子树外的叶子到 $v$ 的距离较 $u$ 要增加 $w$ 。

又良心出题人给的树是满足那个性质的，所以子树内的编号是连续的。

所以最开始 dfs 一遍。求出每个点到根的距离。把询问离线，进行一次先序遍历。

每次进入到一颗子树，就用线段树把该子树内的叶子减少 w 外面的增加 w

当回溯的父亲的时候，就用线段树把该子树内的叶子增加 w 外面的减少 w

然后遍历到一个节点就把和他有关的询问全都用线段树里的信息处理掉就行了

Code

我的实现貌似有点麻烦…我直接用线段树维护叶子，所以每次给出的左右端点还要在叶子序列里二分一下

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>

#define ll long long
#define PI pair
#define Fi first
#define Se second
#define MP make_pair
#define INF 1000000000000000000

using namespace std;

const int N = 500500; 

int n, m, siz[N]; ll dis[N], ans[N];
vector <int> lea;  

struct edge {
  int v; ll w; 
  edge *next; 
} pol[N * 2], *head[N], *cu = pol;

inline void addedge(int u, int v, ll w) {
  edge *p = cu++, *q = cu++;
  p->v = v, p->w = w, p->next = head[u], head[u] = p;
  q->v = u, q->w = w, q->next = head[v], head[v] = q; 
}

inline void dfs(int u, int pre) {
  siz[u] = 1; bool fla = 1; 
  for(edge *p = head[u]; p; p = p->next) {
    int v = p->v; if(v == pre) continue ; 
    fla = 0; dis[v] = dis[u] + p->w;  
    dfs(v, u); siz[u] += siz[v]; 
  } if(fla) lea.push_back(u); 
}

struct ST {
  int l, r; 
  ll tag, mn; 
  ST *ch[2]; 
  inline void seta(ll d) {
    tag += d; mn += d; 
  }
  inline void upd() {
    mn = min(ch[0]->mn, ch[1]->mn); 
  }
  inline void push() {
    if(tag) {
      if(ch[0]) ch[0]->seta(tag);
      if(ch[1]) ch[1]->seta(tag); 
      tag = 0; 
    }
  }
} pool[N * 2], *cur = pool, *rt; 

inline void build(ST *p, int l, int r) {
  p->l = l, p->r = r; 
  if(l == r) {
    p->mn = dis[lea[l - 1]]; 
    return ; 
  }
  ST *ls = cur++, *rs = cur++;
  p->ch[0] = ls, p->ch[1] = rs;
  int mid = (l + r) >> 1;  
  build(ls, l, mid);
  build(rs, mid + 1, r); 
  p->upd(); 
}

inline void modify(ST *p, int l, int r, ll d) {
  if(l > r) return ; 
  if(p->l == l && p->r == r) 
    return p->seta(d); 
  p->push(); 
  if(p->ch[0]->r >= r) modify(p->ch[0], l, r, d);
  else if(p->ch[1]->l <= l) modify(p->ch[1], l, r, d); 
  else modify(p->ch[0], l, p->ch[0]->r, d), 
       modify(p->ch[1], p->ch[1]->l, r, d);
  p->upd(); 
}

inline ll Qmin(ST *p, int l, int r) {
  if(l > r) return INF; p->push(); 
  if(p->l == l && p->r == r) 
    return p->mn; 
  if(p->ch[0]->r >= r) return Qmin(p->ch[0], l, r); 
  else if(p->ch[1]->l <= l) return Qmin(p->ch[1], l, r);
  else return min(Qmin(p->ch[0], l, p->ch[0]->r), 
                  Qmin(p->ch[1], p->ch[1]->l, r)); 
}

vector < PI <int, PI <int, int> > > Q[N]; 

// emm 我还不太会用  lower_bound / upper_bound  所以就只能手写了..

inline int up(int x) {
  int l = 0, r = n - 1, ret = 0; 
  while(l <= r) {
    int mid = (l + r) >> 1;
    if(lea[mid] <= x) 
      l = mid + 1, ret = mid;
    else r = mid - 1; 
  } return ret + 1; 
}

inline int lw(int x) {
  int l = 0, r = n - 1, ret = n - 1; 
  while(l <= r) {
    int mid = (l + r) >> 1; 
    if(lea[mid] >= x)
      r = mid - 1, ret = mid; 
    else l = mid + 1; 
  } return ret + 1; 
}

inline void solve(int u, int pre) {
  for(int i = 0; i < Q[u].size(); i++) {
    int id = Q[u][i].Fi; 
    int l = Q[u][i].Se.Fi;
    int r = Q[u][i].Se.Se; 
    // printf("***%d %d %d\n", id, up(l), lw(r)); 
    ans[id] = Qmin(rt, lw(l), up(r));  
  }
  for(edge *p = head[u]; p; p = p->next) {
    int v = p->v; if(v == pre) continue ; 
    int L = lw(v), R = up(v + siz[v] - 1); 
    ll w = p->w; 
    // printf("%d %d %d\n", v, L, R);
    modify(rt, L, R, -w);
    modify(rt, 1, L - 1, w);
    modify(rt, R + 1, n, w); 
    solve(v, u); 
    modify(rt, L, R, w);
    modify(rt, 1, L - 1, -w); 
    modify(rt, R + 1, n, -w); 
  }
}

int main() {
  scanf("%d %d", &n, &m);
  for(int i = 2; i <= n; i++) {
    int p; ll w; 
    scanf("%d %lld", &p, &w);
    addedge(p, i, w); 
  } dfs(1, 0); n = lea.size(); 
  sort(lea.begin(), lea.end()); 
  build(rt = cur++, 1, n);
  for(int i = 1; i <= m; i++) {
    int v, l, r; 
    scanf("%d %d %d", &v, &l, &r);
    Q[v].push_back(MP(i, MP(l, r))); 
  } solve(1, 0);
  for(int i = 1; i <= m; i++)
    printf("%lld\n", ans[i]); 
  return 0; 
}