该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ）

1   struct Edge{
2       int next;
3       int to;
4       int val;
5   }edge[500050];
6   int head[500050];
7   int now = 1;
8   void push(int st, int ed, int val) {
9       edge[now].val = val;
10      edge[now].to = ed;
11      edge[now].next = head[st];
12      head[st] = now;
13      now++;
14  }
15  int dp1[500050], dp2[500050], n, a, b, val;
16  int dfs1(int root, int fa) {
17      int cnt = 0, ma = 0;
18      for (int i = head[root]; i != 0; i = edge[i].next) {
19          if (edge[i].to == fa) {
20              cnt = edge[i].val;
21          } else {
22              ma = max(ma, dfs1(edge[i].to, root));
23          }
24      }
25      return dp1[root] = cnt + ma;
26  }
27  int dfs2(int root, int fa) {
28      int cnt = 0;
29      for (int i = head[root]; i != 0; i = edge[i].next) {
30          if (edge[i].to != fa) {
31              dp2[root] += dfs2(edge[i].to, root);
32          } else {
33              cnt = edge[i].val;
34          }
35      }
36      for (int i = head[root]; i != 0; i = edge[i].next) {
37          if (edge[i].to != fa) {
38              dp2[root] += dp1[root] - cnt - dp1[edge[i].to];
39          }
40      }
41      return dp2[root];
42  }
43  void solve() {
44      int root;
45      cin >> n >> root;
46      for (int i = 1; i < n ; i++) {
47          cin >> a >> b >> val;
48          push(a, b, val);
49          push(b, a, val);
50      }
51      dfs1(root, -1);
52      dfs2(root, -1);
53      cout << dp2[root] << endl;
54  }

输入的数范围在[1,5*10^5]，其中root,a,b <= n

判断题

1. 51行和52行的-1可以改成0 {{ select(1) }}

• 正确
• 错误

2. 当输入的所有数都为5 $10 ^5$，程序可以正常运行 {{ select(2) }}

• 正确
• 错误

3. 如果删去第20行的内容，dp2[root] 的答案恒定为1 {{ select(3) }}

• 正确
• 错误

4. 当输入为

7 2
1 2 4
3 2 2
3 5 4
4 3 3
4 6 1
7 4 3

答案为8 {{ select(4) }}

• 正确
• 错误

选择题

5. 这段代码的时间复杂度为（）{{ select(5) }}

• O(n)
• O(nlogn)
• O(n$^2$)
• O(n$^2$logn)

6. 当输入为

500000 1
1 2 2
2 3 3
3 4 4
...
...
i i+1 i+1
i+1 i+2 i+2
...
...
499999 500000 500000

输出为（） {{ select(6) }}

• 446198415
• 0
• 125000249999
• 1

7. 当输入为

1023 1
1 2 1
1 3 2
2 4 3
2 5 4
3 6 5
3 7 6
...
...
i i*2 i*2-1
i i*2+1 i*2
i+1 i*2+2 i*2+1
i+1 i*2+3 i*2+2
...
...
511 1022 1021
511 1023 1022

输出为（）(4分) {{ select(7) }}

• 4097
• 0
• 446198415
• 1

完善程序（单选题，每小题 3 分）

(st表)给定一个长度为 n的数列 A$_1$,A$_2$,⋯,A$_n$ 和一个非负整数 x, 给定 m 次查询, 每次询问能否从某个区间[l,r]中选择两个数使得他们的异或等于 x 。其中0$\leq$A$_i$,x$\leq 2 ^ {13}$,1$\leq$n,m $\leq 10 ^ {5}$

#include <iostream>
using namespace std;
int st[100050][30], last[40050],n,m,x,A[100050],l,r;
void solve() {
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        st[i][0] = __1__;
        last[A[i]] = i;
    }
    for (int j = 1; j <= __2__; j++) {
        for (int i = 1; i <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[min(__3__)][j - 1]);
        }
    }
    while (m--) {
        cin >> l >> r;
        int mi = 0, dis = 25, range = l;
        while (range <= r) {
            while ( (1 << dis) > __4__) {
                dis--;
            }
            mi = __5__;
            range += (1 << dis);
        }
        if (mi >= l) {
            cout << "yes\n";
        } else {
            cout << "no\n";
        }
    }
}

1.1处应该填写（）{{ select(8) }}

• A[i]
• A[i] ^ x
• last[A[i]]
• last[A[i] ^ x]

2.2处应该填写（）{{ select(9) }}

• 5
• 14
• 20
• 30

3.3处应该填写（）{{ select(9) }}

• n, i + (1<<(j - 1))
• n,i + (1<<j)
• n, i + j
• n, i * j

4.4处应该填写（）{{ select(10) }}

• r - range
• r - range + 1
• $st[i][dis]$
• $st[i + (1<<dis)][dis]$

5.5处应该填写（）{{ select(11) }}

• $max(mi, st[range + (1 << dis)][dis])$
• $max(mi, st[range][dis])$
• $min(mi, st[range + (1 << dis)][dis])$
• $min(mi, st[range][dis])$