简答题
偏难
#20646
燃烧 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n 。节点 i 的权值为 a i 。…
燃烧
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n 。节点 i 的权值为 ai。
小杨可以选择一个初始节点引燃,每个燃烧的节点会将其相邻节点中权值严格小于自身权值的节点也引燃,火焰会在节点间扩散直到不会有新的节点被引燃。
小杨想知道在合理选择初始节点的情况下,最多可以燃烧多少个节点。
输入格式
第一行包含一个正整数 n ,代表节点数量。
第二行包含 n 个正整数 a1,a2,...,an,代表节点权值。
之后 n−1 行,每行包含两个正整数 ui,vi,代表存在一条连接节点 ui和 vi的边。
输出格式
输出一个正整数,代表最多燃烧的节点个数。
输入样例
输出样例

对于全部数据,保证有 1≤n≤105,1≤ai≤106。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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";
}</pre>
这道题暂未补解析。