A29813. 燃烧
填空题
困难
知识点
题目描述
燃烧
时间限制：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
参考答案
#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";
}
上一题
下一题