首页 › 题库 › GESP编程能力等级认证 › GESP-C++七级

GESP-C++七级 题库

共 270 道题 ,第 13 / 14 页 · 按题型筛选,点「查看答案」核对解析
241 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

C++ 语言中,表达式 4 ^ 2 的结果类型为 int ,值为 6 。

A
正确
B
错误
答案与解析
正确答案:对
分析表达式中运算符的语义:'^' 在 C++ 中为按位异或运算符,非数学幂运算;确定操作数类型:4 和 2 均为整型字面量,默认类型为 int;根据 C++ 类型规则,两个 int 操作数进行按位异或运算,结果类型仍为 int;按位异或运算的执行基于二进制位逐位计算,参与运算的两个整数转换为二进制形式后,相同位值为 0,不同位值为 1,最终合成结果整数。
题目详情
242 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

C++ 中引用可以重新绑定。

A
正确
B
错误
答案与解析
正确答案:错
引用在C++中是别名机制,绑定到初始化时指定的对象后无法更改。引用必须在定义时初始化,且不能重新指向其他对象。重新绑定意味着解除当前绑定并关联新对象,这与引用的底层实现机制冲突。指针可通过赋值改变所指向地址,但引用不具备此操作。语言标准规定引用一经绑定即固定,无语法支持重新绑定。任何试图修改引用的行为实际是对所绑定对象的操作。
题目详情
243 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

在 C++ 中,若函数形参为引用类型,则在函数内部对该形参的修改会影响对应的实参。

A
正确
B
错误
答案与解析
正确答案:对
在C++中,当函数形参为引用类型时,该形参成为实参的别名,二者绑定至同一内存地址。引用本身不分配独立存储空间,所有对形参的操作直接作用于原对象。函数调用时,实参被用来初始化引用形参,建立绑定关系。一旦绑定完成,对引用形参的读取或修改均等效于对实参本身的读取或修改。此机制由编译器保障,无需运行时额外解引用操作。引用形参的存在使得函数能够访问并改变外部对象的状态,其行为由语言标准明确规定,与指针不同,引用一经初始化不可重新绑定。
题目详情
244 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

如果一个最值问题可以用动态规划在多项式时间内求解,那么也一定存在一种贪心策略,可以在多项式时间 内求得最优解。

A
正确
B
错误
答案与解析
正确答案:错
动态规划适用于具有最优子结构和重叠子问题的问题,通过自底向上求解所有子问题保证全局最优。贪心算法基于贪心选择性质,在每一步选择局部最优,期望达到全局最优,其正确性依赖于问题是否满足贪心选择性和最优子结构。两个算法的适用条件不同:动态规划能解决的问题不一定满足贪心选择性质,因此无法保证存在贪心策略得到最优解。判断时需分析两类算法对问题结构性质的要求差异,不能由动态规划可解推出贪心策略必然存在。
题目详情
245 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

使用归并排序对 个元素进行排序时,无论最好、最坏还是平均情况,时间复杂度均为

A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
246 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

在无向连通图中删除一条边,该图就一定变成非连通图。

A
正确
B
错误
答案与解析
正确答案:错
分析无向连通图中边的性质,区分桥边与非桥边。桥边是唯一连接两个连通分量的边,删除后图不再连通;非桥边存在于环中,其删除不会破坏图的连通性。判断删除某条边是否导致图不连通,需考察该边是否属于图中的某个环。若边在环中,则存在替代路径保持连通;若边不在任何环中,则为桥边,删除后图分裂为两个连通分量。因此,边的删除对连通性的影响由其在图结构中的位置决定。
题目详情
247 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

在一个无向图中,每个顶点有不同的编号,在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号更小的相邻顶点,则从指定顶点开始的遍历序列是唯一的。

A
正确
B
错误
答案与解析
正确答案:对
深度优先遍历从指定顶点开始,访问当前顶点后,依次选择未被访问的相邻顶点进行递归遍历。当存在多个未访问的相邻顶点时,选择编号最小的顶点作为下一个访问对象。该选择策略在每一步都具有确定性,即在相同状态下每次执行都会选取同一顶点。遍历过程中顶点的访问顺序由起始顶点和每一步的邻接顶点选择规则共同决定。图的结构和顶点编号唯一确定了每一步可选的相邻顶点集合及其排序。由于每一步的选择均依据编号大小进行比较并取最小值,不存在随机或并列情况下的任意选取。因此,从同一顶点出发,按照此规则生成的遍历序列由图的连接关系和顶点编号完全决定。
题目详情
248 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

若所有字符出现频率相同,则哈夫曼编码一定会得到完全二叉树

A
正确
B
错误
答案与解析
正确答案:错
分析字符频率相同时哈夫曼树构建过程中每次选择两个最小频率节点合并的机制;考察该过程是否必然使所有非叶节点都有两个子节点;结合完全二叉树定义,即除最后一层外每层节点均满,且最后一层节点靠左连续排列,判断该结构在等频条件下是否唯一确定;考虑当所有字符频率相同且字符数为2的幂次或非2的幂次时,构建过程中是否存在必须补全左右子树的情况;根据哈夫曼算法的贪心策略,相同频率下任意选取两个节点不影响后续结构生成的可能性。
题目详情
249 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

使用 math.h 或 cmath 头文件中的函数,表达式 sin(90) 的结果为 1 。

A
正确
B
错误
答案与解析
正确答案:错
分析表达式 sin(90) 的计算过程:math.h 或 cmath 中的三角函数接受弧度制输入;角度值 90 需转换为弧度才能得到对应正弦值;直接传入整数 90 视为弧度输入,不等于 π/2 弧度的精确值;标准库函数按 IEEE 浮点规范执行计算,结果为 sin(90 radians),非 sin(90°);若需计算角度制正弦值,需将角度乘以 π/180 转换为弧度后再传入函数。
题目详情
250 判断题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

在一个无向连通图中,从任意顶点开始进行深度优先遍历,最终得到的 DFS 生成树一定包含图中的所有顶 点。

A
正确
B
错误
答案与解析
正确答案:对
深度优先遍历从指定起始顶点出发,沿边访问可达顶点,每条被遍历的边加入生成树。遍历过程中,未访问的相邻顶点被递归访问,直至所有从起始点可达的顶点均被处理。无向连通图中任意顶点对之间存在路径,因此从任一顶点出发的 DFS 可访问全部顶点。生成树由遍历过程中实际使用的边构成,覆盖所有被访问顶点。由于图连通,所有顶点均被访问,故生成树包含全部顶点。遍历顺序不影响顶点覆盖性,只影响边的选择。生成树结构依赖于遍历路径,但顶点集合始终为全集。
题目详情
251 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

城市规划

题目描述

A 国有n座城市,城市之间由m条双向道路连接,任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1,2....,n编号。第i(1≤i≤m)条双向道路连接城市ui与城市vi。

对于城市u和城市v而言,它们之间的连通度d(u,v)定义为从城市u出发到达城市 所需经过的双向道路的最少条数。由于道路是双向的,可以知道连通度满足d(u,v)=d(v,u),特殊地有d(u,u)=0。

现在 A 国正在规划城市建设方案。城市u的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市,如果有多个满足条件的城市,则选取其中编号最小的城市。形式化地,你需要求出使得max1≤i≤nd(u,i)最小的u,若存在多个可能的u则选取其中最小的。

输入格式

第一行,两个正整数n,m,表示 A 国的城市数量与双向道路数量。

接下来m行,每行两个整数ui,vi,表示一条连接城市ui与城市vi的双向道路。

输出格式

输出一行,一个整数,表示建设难度最小的城市编号。如果有多个满足条件的城市,则选取其中编号最小的城市。

输入样例 1

3 3
1 2
1 3
2 3

输出样例 1

1

输入样例 2

4 4
1 2
2 3
3 4
2 4

输出样例 2

2

数据范围

对于40的测试点,保证1≤n≤300 。

对于所有测试点,保证1≤n≤2000,1≤m≤2000,1≤ui,vi≤n。

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 2005;
int n, m;
vector<int> e[N];
int d[N], mx[N], q[N];

void bfs(int u) {
    for (int i = 1; i <= n; i++)
        d[i] = n + 1;
    d[u] = 0;
    q[1] = u;
    int ql = 1, qr = 1;
    while (ql <= qr) {
        int x = q[ql++];
        for (auto y : e[x])
            if (d[x] + 1 < d[y]) {
                d[y] = d[x] + 1;
                q[++qr] = y;
            }
    }
    mx[u] = d[q[qr]];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        bfs(i);
        if (mx[i] < mx[ans])
            ans = i;
    }
    printf("%d\n", ans);
    return 0;
}
题目详情
252 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

学习小组

时间限制:1.0 s

内存限制:512.0 MB

输入样例 1

4
2 1 3 2
1 5 6 3

输出样例 1

12

输入样例 2

8
1 3 2 4 3 5 4 6
0 2 5 6 4 3 3 4

输出样例 2

21

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 305;
int n;
int c[N], a[N];
int f[N][N];
int ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    sort(c + 1, c + n + 1);
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= n; j++)
            for (int k = i; k <= n; k++) {
                int diff = 0;
                if (i > 1)
                    diff = c[n - j + 1] - c[j];
                f[j][k] = max(f[j][k], f[j - 1][k - i] + a[i] + diff);
                if (k == n)
                    ans = max(ans, f[j][k]);
            }
    
    printf("%d\n", ans);
    return 0;
}
题目详情
253 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

连通图

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 100005;
int n, m;
int f[N];
int ans;

// 带路径压缩的并查集查找
int getf(int u) {
    if (!f[u]) 
        return u;
    return f[u] = getf(f[u]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        int fu = getf(u);
        int fv = getf(v);
        if (fu != fv) {
            f[fu] = fv;
        }
    }
    // 统计连通块数量:根节点数量
    ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (getf(i) == i)
            ans++;
    }
    // 连通块数-1 = 最少需要添加的边(生成树边数)
    printf("%d\n", ans - 1);
    return 0;
}
题目详情
254 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

金币收集

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;

const int INF = 2e9;
const int N = 100005;

int n;
int x[N], t[N];
int p[N], f[N];
int mx;

// 排序规则:先按x升序,x相同则按t升序
bool cmp(int a, int b) {
    if (x[a] != x[b])
        return x[a] < x[b];
    return t[a] < t[b];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &x[i], &t[i]);
        t[i] -= x[i];  // 转换为 t' = t - x
        p[i] = i;      // 下标数组,用于排序
        f[i] = INF;
    }
    // 按x从小到大排序所有点
    sort(p + 1, p + n + 1, cmp);
    
    mx = 0;
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
        int val = t[p[i]];
        if (val < 0) continue; // 负数直接无法选取
        
        // 二分查找最大长度r,满足 f[r] <= val
        int l = 0, r = mx;
        while (l < r) {
            int mid = (l + r) / 2 + 1;
            if (val < f[mid])
                r = mid - 1;
            else
                l = mid;
        }
        // 可以拼出长度 r+1 的子序列
        mx = max(mx, r + 1);
        if (val < f[r + 1]) {
            f[r + 1] = val;
        }
    }
    printf("%d\n", mx);
    return 0;
}
题目详情
255 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

线图

时间限制:1 s,内存限制:512 MB

【问题描述】

给定由 n 个结点与 m 条边构成的简单无向图 G,结点依次以 1、2、……、n 编号。简单无向图意味着 G 中不包含重边与自环。G 的线图 L(G) 通过以下方式构建:

(1)初始时线图 L(G) 为空。

(2)对于无向图 G 中的一条边,在线图 L(G) 中加入与之对应的一个结点。

(3)对于无向图 G 中两条不同的边 (u1, v1)、(u2, v2),若存在 G 中的结点同时连接这两条边(即 u1, v1之一与 u2, v2之一相同),则在线图 L(G) 中加入一条无向边,连接  (u1, v1)、(u2, v2) 在线图中对应的结点。

请你求出线图 L(G) 中所包含的无向边的数量。

【输入描述】

第一行,两个正整数 n、m,分别表示无向图 G 中的结点数与边数。

接下来 m 行,每行两个正整数 ui、vi,表示 G 中连接 ui、vi 的一条无向边。

【输出描述】

输出共一行,一个整数,表示线图 L(G) 中所包含的无向边的数量。

【样例输入1】

5 4
1 2
2 3
3 1
4 5

【样例输出1】

3

【样例输入2】

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

【样例输出2】

30

【样例解释1】

【数据范围】

对于60%测试点,保证 1 <= n、m <= 500。

对于所有测试点,保证 1 <= n、m <= 100000。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int n, m, deg[N];
long long ans;
int main() {
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
    }
    for (int i = 1; i <= n; i++)
        ans += 1ll * deg[i] * (deg[i] - 1) / 2;
    cout << ans;
    return 0;
}
题目详情
256 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

调味平衡

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 准备了 n 种食材用来制作料理,这些食材依次以 1、2、……、n 编号,第 i 种食材的酸度为 ai,甜度为 bi。

对于每种食材,小 A 可以选择将其放入料理,或者不放入料理。料理的酸度 A 为放入食材的酸度之和,甜度 B 为放入食材的甜度之和。如果料理的酸度与甜度相等,那么料理的调味是平衡的。

过于清淡的料理并不好吃,因此小 A 想在满足料理调味平衡的前提下,合理选择食材,最大化料理的酸度与甜度之和。

你能帮他求出在调味平衡的前提下,料理酸度与甜度之和的最大值吗?

【输入描述】

第一行,一个正整数 n,表示食材种类数量。

接下来 n 行,每行两个正整数 ai、bi,表示食材的酸度与甜度。

【输出描述】

输出共一行,一个整数,表示在调味平衡的前提下,料理酸度与甜度之和的最大值。

【样例输入1】

3
1 2
2 4
3 2

【样例输出1】

8

【样例输入2】

5
1 1
2 3
6 1
8 2
5 7

【样例输出2】

2

【数据范围】

对于40%的测试点,保证 1 <= n <= 10,1 <= ai、bi <= 10。

对于另外20%的测试点,保证 1 <= n <= 50,1 <= ai、bi <= 10。

对于所有测试点,保证 1 <= n <= 100,1 <= ai、bi <= 500。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 105;
const int C = 505;
const int D = N * C * 2;
int n, f[D];
int main() {
    cin >> n;
    for (int i = 0; i < D; i++)
        f[i] = -1e9;
    f[N * C] = 0;
    while (n--) {
        int a, b;
        cin >> a >> b;
        int x = a + b, y = a - b;
        if (y <= 0) {
            for (int i = -y; i < D; i++)
                f[i + y] = max(f[i + y], f[i] + x);
        } else {
            for (int i = D - y - 1; i; i--)
                f[i + y] = max(f[i + y], f[i] + x);
        }
    }
    cout << f[N * C] << endl;
    return 0;
}
题目详情
257 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

图上移动

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 有一张包含 个n 结点与 m 条边的无向图,结点以 1、2、……、n 标号。

小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前小 A 所在结点相邻的结点。

对于每个结点 i(1<=i<=n),小 A 想知道从结点 i 出发恰好移动步1、2、……、k 之后,小 A 可能位于哪些结点。

由于满足条件的结点可能有很多,你只需要求出这些结点的数量。

【输入描述】

第一行,三个正整数 n、m、k,分别表示无向图的结点数与边数,最多移动的步数。

接下来 m 行,每行两个正整数 ui、vi,表示图中的一条连接结点 ui 与 vi 的无向边。

【输出描述】

共 n 行,第 i 行(1<=i<=n )包含 k 个整数,第 j 个整数( 1<=j<=k)表示从结点 i 出发恰好移动 j 步之后可能位于的结点数量。

【样例输入1】

4 4 3
1 2
1 3
2 3
3 4

【样例输出1】

2 4 4
2 4 4
3 3 4
1 3 3

【数据范围】

对于 20% 的测试点,保证 k=1。

对于另外 20% 的测试点,保证 1<=n<=50,1<=m<=50 。

对于所有测试点,保证 1<=n<=500,1<=m<=500 ,1<=k<=20 ,1<=ui、vi<=n 。

答案与解析
参考答案
#include <cstdio>
using namespace std;
const int K = 25;
const int N = 505;
const int E = N << 1;
int n, m, k;
int h[N], to[E], nx[E], et;
int f[K][N][N];
void ae(int u, int v) {
    et++;
    to[et] = v;
    nx[et] = h[u];
    h[u] = et;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        ae(u, v);
        ae(v, u);
    }
    for (int i = 1; i <= n; i++)
        f[0][i][i] = 1;
    for (int t = 1; t <= k; t++)
        for (int x = 1; x <= n; x++)
            for (int y = 1; y <= n; y++)
                if (f[t - 1][x][y])
                    for (int i = h[y]; i; i = nx[i])
                        f[t][x][to[i]] = 1;
    for (int i = 1; i <= n; i++) {
        for (int t = 1; t <= k; t++) {
            int ans = 0;
            for (int j = 1; j <= n; j++)
                ans += f[t][i][j];
            printf("%d%c", ans, " \n"[t == k]);
        }
    }
    return 0;
}
题目详情
258 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

等价消除

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 有一个仅包含小写英文字母的字符串 。

对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字符串是可以被等价消除的。

小 A 想知道 S 有多少子串是可以被等价消除的。

一个字符串 S' 是 S 的子串,当且仅当删去 S 的某个可以为空的前缀和某个可以为空的后缀之后,可以得到 S'。

【输入描述】

第一行,一个正整数 |S|,表示字符串 S 的长度。

第二行,一个仅包含小写英文字母的字符串 S。

【输出描述】

一行,一个整数,表示答案。

【样例输入1】

7
aaaaabb

【样例输出1】

9

【样例输入2】

9
babacabab

【样例输出2】

2

【数据范围】

对于 20% 的测试点,保证 S 中仅包含 a 和 b 两种字符。

对于另外 20% 的测试点,保证 1<=|S|<=2000。

对于所有测试点,保证 1<=|S|<=200000。

答案与解析
参考答案
#include <cstdio>
#include <map>
using namespace std;
const int N = 2e5 + 5;
int n;
char s[N];
map <int, int> m;
long long ans;
int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    int v = 0;
    m[v]++;
    for (int i = 1; i <= n; i++) {
        v ^= 1 << (s[i] - 'a');
        ans += m[v];
        m[v]++;
    }
    printf("%lld\n", ans);
    return 0;
}
题目详情
259 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

武器购买

时间限制:1.0 s

内存限制:512.0 MB

题面描述

商店里有 n 个武器,第 i 个武器的强度为 pi,花费为 ci。

小杨想要购买一些武器,满足这些武器的总强度不小于 P ,总花费不超过 Q ,小杨想知道是否存在满足条件的购买方案,如果有,最少花费又是多少。

输入格式

第一行包含一个正整数 t ,代表测试数据组数。

对于每组测试数据,第一行包含三个正整数 n,P,Q,含义如题面所示。

之后 n 行,每行包含两个正整数 pi,ci,代表武器的强度和花费。

输出格式

对于每组测试数据,如果存在满足条件的购买方案,输出最少花费,否则输出 -1。


输入样例

3
3 2 3
1 2
1 2
2 3
3 3 4
1 2
1 2
2 3
3 1000 1000
1 2
1 2
2 3

输出样例

3
-1
-1

对于全部数据,保证有 1≤t≤10,1≤n≤100,1≤pi,ci,P,Q≤5×104。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

#define ll long long
ll dp[50010];
ll solve(int n, int P, int Q, vector<pair<int, int>>& weapons) {
	dp[0] = 0;
	
	for (auto& weapon : weapons) {
		int p = weapon.first;
		int c = weapon.second;
		for (int j = Q; j >= c; --j) {
			if (dp[j - c]>=0) {
				dp[j] = max(dp[j], dp[j - c] + p);
			}
		}
	}
	for (int j = 0; j <= Q; ++j) {
		if (dp[j] >= P) {
			return j;
		}
	}
	
	return -1;
}

int main() {
	int t;
	cin>>t;
	while(t--){
		int n, P, Q;
		cin >> n >> P >> Q;
		memset(dp,-0x3f,sizeof dp);
		vector<pair<int, int> > weapons(n);
		for (int i = 0; i < n; ++i) {
			cin >> weapons[i].first >> weapons[i].second;
		}
		cout << solve(n, P, Q, weapons) << "\n";
	}
	return 0;
}
题目详情
260 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

燃烧

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n 。节点 i 的权值为 ai。

小杨可以选择一个初始节点引燃,每个燃烧的节点会将其相邻节点中权值严格小于自身权值的节点也引燃,火焰会在节点间扩散直到不会有新的节点被引燃。

小杨想知道在合理选择初始节点的情况下,最多可以燃烧多少个节点。

输入格式

第一行包含一个正整数 n ,代表节点数量。

第二行包含 n 个正整数 a1,a2,...,an,代表节点权值。

之后 n−1 行,每行包含两个正整数 ui,vi,代表存在一条连接节点 ui和 vi的边。

输出格式

输出一个正整数,代表最多燃烧的节点个数。


输入样例

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

输出样例

3

对于全部数据,保证有 1≤n≤105,1≤ai≤106。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int sum[N];
int down[N];
vector<int> g[N];
void dfs_down(int x,int fa){
	down[x]=1;
	for(int i:g[x]){
		if(i!=fa){
			dfs_down(i,x);
			if(a[x]>a[i]){
				down[x]+=down[i];
			}
		}
	}
}
void dfs_sum(int x,int fa){
	if(a[x]>a[fa]){
		sum[x]+=sum[fa]+down[fa];
	}
	for(int i:g[x]){
		if(i!=fa){
			dfs_sum(i,x);
		}
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs_down(1,0);
	dfs_sum(1,0);
	int mx = 0;
	for(int i=1;i<=n;i++){
		mx = max(mx,sum[i]+down[i]);
	}
	cout<<mx<<"\n";
}
题目详情