拼多多笔试真题-多多的审批链(C++/Py/Java /Js/Go)

多多的审批链

拼多多技术岗 4月26号笔试 第四题

题目内容

多多的部门中发起审批单有一套审批流程，审批关系可以抽象为一棵以 111 号节点为根的树，共有 nnn 个节点。对于每个 i(2≤i≤n)i(2 \le i \le n)i(2≤i≤n)，给定它的直属上级 pip_ipi​，即审批树中存在一条从 pip_ipi​ 到 iii 的边。
对于任意节点 uuu，如果它发起一张审批单，那么审批单只能先提交给它的直属上级，再继续逐级上报到更高层。
现在多多最多可以选择 kkk 个节点作为“关键审批节点”。如果审批单从 uuu 出发，向上经过不超过 DDD 条边，就能够到达某个关键审批节点，则称节点 uuu 被覆盖。
请帮多多找到，在最多选择 kkk 个关键审批节点的前提下，求出满足条件的最小 DDD，使得整棵审批树上的所有节点都被覆盖。

输入描述

第一行输入一个整数 T(1≤T≤3)T(1 \le T \le 3)T(1≤T≤3)，表示数据组数。 接下来对于每组数据：

• 第一行包含两个整数 n(1≤n≤2×105)n(1 \le n \le 2 \times 10^5)n(1≤n≤2×105) 和 k(1≤k≤n)k(1 \le k \le n)k(1≤k≤n)。
• 第二行包含 n−1n-1n−1 个整数 p2,p3,…,pnp_2, p_3, \dots, p_np2​,p3​,…,pn​，其中 pip_ipi​ 表示节点 iii 的父节点。

输出描述

对于每组数据，仅输出一行整数，表示满足条件的最小 DDD。

样例1

输入

11
27 2
31 1 2 2 3 3
4

输出

12
2

说明
可以把节点 111 和 222 设置为关键审批节点。

• 节点 1、21、21、2 自身被覆盖；
• 节点 333 向上走 111 条边可以到达节点 111；
• 节点 4、54、54、5 向上走 111 条边可以到达节点 222；
• 节点 6、76、76、7 向上走 222 条边可以到达节点 111。

样例2

输入

11
25 1
31 2 3 4
4

输出

14
2

说明
这是一条长度为 444 的链。
如果只能选择 111 个关键审批节点，那么根节点 111 必须被选中，否则根本自身无法被覆盖。
此时最深的节点 555 到节点 111 的距离为 444，因此答案为 444。

题解

思路

解题思路二分 + 树状数组 + 贪心

1. 二分答案最小距离，贪心从最深未覆盖节点出发，把关键节点放在它向上D层（D级祖先节点）的位置，用 DFS 序 + 树状数组快速维护哪些节点已经被覆盖。
2. 其中DFS序和BIT的作用是为了快速得出哪些节点已经被覆盖。利用DFS序，可以快速知道关键节点覆盖的子树节点区间范围，然后通过树状数组区间前缀和差可快速知道节点是否被覆盖。
3. 同时为了快速知道最深未覆盖节点d级祖先节点可通过倍增数组up实现。
4. 算法总体时间复杂度为O(nlog2n)

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4
5// 树状数组：区间加，单点查询
6struct BIT {
7    int n;
8    vector<int> tree;
9
10    BIT(int n = 0) {
11        init(n);
12    }
13
14    void init(int n) {
15        this->n = n;
16        tree.assign(n + 2, 0);
17    }
18
19    void add(int x, int v) {
20        while (x <= n) {
21            tree[x] += v;
22            x += x & -x;
23        }
24    }
25
26    // 区间[l,r]增加v
27    void rangeAdd(int l, int r, int v) {
28        add(l, v);
29        add(r + 1, -v);
30    }
31
32    // 查询单点
33    int query(int x) {
34        int res = 0;
35        while (x > 0) {
36            res += tree[x];
37            x -= x & -x;
38        }
39        return res;
40    }
41};
42
43
44int n, k;
45int LOG;
46
47vector<vector<int>> g;
48vector<vector<int>> up;
49
50vector<int> depth;
51// 子树第一次被访问编号 遍历完子树最大访问编号
52vector<int> tin, tout;
53// 遍历顺序
54vector<int> order;
55
56int timerCnt;
57
58
59// DFS序 + 倍增第一层
60void dfs(int u) {
61    tin[u] = ++timerCnt;
62    order.push_back(u);
63
64    for (int v : g[u]) {
65        depth[v] = depth[u] + 1;
66        up[0][v] = u;
67        dfs(v);
68    }
69
70    tout[u] = timerCnt;
71}
72
73
74// u向上走d步
75int jump(int u, int d) {
76    for (int i = 0; i < LOG; i++) {
77        if (d & (1 << i)) {
78            u = up[i][u];
79
80            // 超过根节点
81            if (u == 0) {
82                return 1;
83            }
84        }
85    }
86    return u;
87}
88
89
90// 判断D是否可行
91bool check(int D) {
92
93    BIT bit(n + 2);
94
95    int cnt = 0;
96
97    // 深度大的节点优先处理
98    for (int u : order) {
99        // 当前节点已经被覆盖
100        if (bit.query(tin[u]) > 0) {
101            continue;
102        }
103        // 当前节点没有覆盖
104        // 选择u向上D步的位置作为关键节点
105        int x = jump(u, D);
106        cnt++;
107        if (cnt > k) {
108            return false;
109        }
110        // 关键节点x覆盖自己的子树
111        bit.rangeAdd(tin[x], tout[x], 1);
112    }
113    return true;
114}
115
116
117int main() {
118    ios::sync_with_stdio(false);
119    cin.tie(nullptr);
120    int T;
121    cin >> T;
122
123    while (T--) {
124        cin >> n >> k;
125        g.assign(n + 1, {});
126
127        for (int i = 2; i <= n; i++) {
128            int p;
129            cin >> p;
130            g[p].push_back(i);
131        }
132
133
134        LOG = 1;
135        while ((1 << LOG) <= n) {
136            LOG++;
137        }
138
139
140        up.assign(LOG, vector<int>(n + 1));
141
142        depth.assign(n + 1, 0);
143        tin.assign(n + 1, 0);
144        tout.assign(n + 1, 0);
145
146        order.clear();
147
148        timerCnt = 0;
149
150
151        dfs(1);
152
153        // 倍增表
154        for (int j = 1; j < LOG; j++) {
155            for (int i = 1; i <= n; i++) {
156                up[j][i] = up[j - 1][up[j - 1][i]];
157            }
158        }
159
160
161        // 深度降序
162        sort(order.begin(), order.end(),
163             [&](int a, int b) {
164                 return depth[a] > depth[b];
165        });
166
167        int l = 0;
168        int r = n;
169        int ans = n;
170        // 二分答案
171        while (l <= r) {
172            int mid = (l + r) / 2;
173            if (check(mid)) {
174                ans = mid;
175                r = mid - 1;
176            } else {
177                l = mid + 1;
178            }
179        }
180        cout << ans << '\n';
181    }
182
183
184    return 0;
185}
186

java

1import java.io.*;
2import java.util.*;
3
4public class Main {
5
6    // 树状数组：区间加，单点查询
7    static class BIT {
8        int n;
9        int[] tree;
10
11        BIT(int n) {
12            this.n = n;
13            tree = new int[n + 2];
14        }
15
16        void add(int x, int v) {
17            while (x <= n) {
18                tree[x] += v;
19                x += x & -x;
20            }
21        }
22
23        // 区间[l,r]增加v
24        void rangeAdd(int l, int r, int v) {
25            add(l, v);
26            add(r + 1, -v);
27        }
28
29        // 查询单点
30        int query(int x) {
31            int res = 0;
32            while (x > 0) {
33                res += tree[x];
34                x -= x & -x;
35            }
36            return res;
37        }
38    }
39
40
41    static int n, k;
42    static int LOG;
43
44    static ArrayList<Integer>[] g;
45    static int[][] up;
46
47    static int[] depth;
48
49    // 子树第一次被访问编号 遍历完子树最大访问编号
50    static int[] tin, tout;
51
52    // 遍历顺序
53    static ArrayList<Integer> order;
54
55    static int timerCnt;
56
57
58    // DFS序 + 倍增第一层
59    static void dfs(int u) {
60        tin[u] = ++timerCnt;
61        order.add(u);
62
63        for (int v : g[u]) {
64            depth[v] = depth[u] + 1;
65            up[0][v] = u;
66            dfs(v);
67        }
68
69        tout[u] = timerCnt;
70    }
71
72
73    // u向上走d步
74    static int jump(int u, int d) {
75        for (int i = 0; i < LOG; i++) {
76            if ((d & (1 << i)) != 0) {
77                u = up[i][u];
78
79                // 超过根节点
80                if (u == 0) {
81                    return 1;
82                }
83            }
84        }
85        return u;
86    }
87
88
89    // 判断D是否可行
90    static boolean check(int D) {
91
92        BIT bit = new BIT(n + 2);
93
94        int cnt = 0;
95
96        // 深度大的节点优先处理
97        for (int u : order) {
98
99            // 当前节点已经被覆盖
100            if (bit.query(tin[u]) > 0) {
101                continue;
102            }
103
104
105            // 当前节点没有覆盖
106            // 选择u向上D步的位置作为关键节点
107            int x = jump(u, D);
108
109            cnt++;
110
111            if (cnt > k) {
112                return false;
113            }
114
115
116            // 关键节点x覆盖自己的子树
117            bit.rangeAdd(tin[x], tout[x], 1);
118        }
119
120        return true;
121    }
122
123
124    public static void main(String[] args) throws Exception {
125
126        FastScanner fs = new FastScanner(System.in);
127
128        StringBuilder sb = new StringBuilder();
129
130        int T = fs.nextInt();
131
132        while (T-- > 0) {
133
134            n = fs.nextInt();
135            k = fs.nextInt();
136
137
138            g = new ArrayList[n + 1];
139
140            for (int i = 1; i <= n; i++) {
141                g[i] = new ArrayList<>();
142            }
143
144
145            for (int i = 2; i <= n; i++) {
146                int p = fs.nextInt();
147                g[p].add(i);
148            }
149
150
151            LOG = 1;
152            while ((1 << LOG) <= n) {
153                LOG++;
154            }
155
156
157            up = new int[LOG][n + 1];
158
159            depth = new int[n + 1];
160
161            tin = new int[n + 1];
162            tout = new int[n + 1];
163
164
165            order = new ArrayList<>();
166
167            timerCnt = 0;
168
169
170            dfs(1);
171
172
173            // 倍增表
174            for (int j = 1; j < LOG; j++) {
175                for (int i = 1; i <= n; i++) {
176                    up[j][i] = up[j - 1][up[j - 1][i]];
177                }
178            }
179
180
181            // 深度降序
182            order.sort((a, b) -> depth[b] - depth[a]);
183
184
185            int l = 0;
186            int r = n;
187            int ans = n;
188
189
190            // 二分答案
191            while (l <= r) {
192
193                int mid = (l + r) / 2;
194
195                if (check(mid)) {
196                    ans = mid;
197                    r = mid - 1;
198                } else {
199                    l = mid + 1;
200                }
201            }
202
203
204            sb.append(ans).append('\n');
205        }
206
207
208        System.out.print(sb);
209    }
210
211
212    static class FastScanner {
213
214        private final InputStream in;
215        private final byte[] buffer = new byte[1 << 16];
216        private int ptr = 0, len = 0;
217
218
219        FastScanner(InputStream is) {
220            in = is;
221        }
222
223
224        int read() throws IOException {
225            if (ptr >= len) {
226                len = in.read(buffer);
227                ptr = 0;
228
229                if (len <= 0)
230                    return -1;
231            }
232
233            return buffer[ptr++];
234        }
235
236
237        int nextInt() throws IOException {
238
239            int c;
240
241            do {
242                c = read();
243            } while (c <= ' ');
244
245
246            int sign = 1;
247
248            if (c == '-') {
249                sign = -1;
250                c = read();
251            }
252
253
254            int val = 0;
255
256            while (c > ' ') {
257                val = val * 10 + c - '0';
258                c = read();
259            }
260
261            return val * sign;
262        }
263    }
264}
265

python

1import sys
2
3sys.setrecursionlimit(1 << 25)
4
5
6# 树状数组：区间加，单点查询
7class BIT:
8
9    def __init__(self, n):
10        self.n = n
11        self.tree = [0] * (n + 2)
12
13    def add(self, x, v):
14        while x <= self.n:
15            self.tree[x] += v
16            x += x & -x
17
18    # 区间[l,r]增加v
19    def rangeAdd(self, l, r, v):
20        self.add(l, v)
21        self.add(r + 1, -v)
22
23    # 查询单点
24    def query(self, x):
25        res = 0
26        while x > 0:
27            res += self.tree[x]
28            x -= x & -x
29        return res
30
31
32def main():
33
34    data = list(map(int, sys.stdin.buffer.read().split()))
35    idx = 0
36
37    T = data[idx]
38    idx += 1
39
40    ans_list = []
41
42    for _ in range(T):
43
44        n = data[idx]
45        k = data[idx + 1]
46        idx += 2
47
48
49        g = [[] for _ in range(n + 1)]
50
51        for i in range(2, n + 1):
52            p = data[idx]
53            idx += 1
54            g[p].append(i)
55
56
57        LOG = 1
58        while (1 << LOG) <= n:
59            LOG += 1
60
61
62        up = [[0] * (n + 1) for _ in range(LOG)]
63
64        depth = [0] * (n + 1)
65
66        # 子树第一次被访问编号 遍历完子树最大访问编号
67        tin = [0] * (n + 1)
68        tout = [0] * (n + 1)
69
70        # 遍历顺序
71        order = []
72
73        timer = 0
74
75
76        def dfs(u):
77
78            nonlocal timer
79
80            timer += 1
81            tin[u] = timer
82            order.append(u)
83
84            for v in g[u]:
85                depth[v] = depth[u] + 1
86                up[0][v] = u
87                dfs(v)
88
89            tout[u] = timer
90
91
92        # DFS序 + 倍增第一层
93        dfs(1)
94
95
96        # 倍增表
97        for j in range(1, LOG):
98            for i in range(1, n + 1):
99                up[j][i] = up[j - 1][up[j - 1][i]]
100
101
102        # 深度降序
103        order.sort(key=lambda x: depth[x], reverse=True)
104
105
106        def jump(u, d):
107
108            # u向上走d步
109            for i in range(LOG):
110                if d & (1 << i):
111                    u = up[i][u]
112
113                    # 超过根节点
114                    if u == 0:
115                        return 1
116
117            return u
118
119
120        def check(D):
121
122            bit = BIT(n + 2)
123
124            cnt = 0
125
126            # 深度大的节点优先处理
127            for u in order:
128
129                # 当前节点已经被覆盖
130                if bit.query(tin[u]) > 0:
131                    continue
132
133
134                # 当前节点没有覆盖
135                # 选择u向上D步的位置作为关键节点
136                x = jump(u, D)
137
138                cnt += 1
139
140                if cnt > k:
141                    return False
142
143
144                # 关键节点x覆盖自己的子树
145                bit.rangeAdd(tin[x], tout[x], 1)
146
147            return True
148
149
150        l, r = 0, n
151        ans = n
152
153
154        # 二分答案
155        while l <= r:
156
157            mid = (l + r) // 2
158
159            if check(mid):
160                ans = mid
161                r = mid - 1
162            else:
163                l = mid + 1
164
165
166        ans_list.append(str(ans))
167
168
169    print("\n".join(ans_list))
170
171
172if __name__ == "__main__":
173    main()
174