题目描述
对于所有数据,满足2<=n<=50000,1<=a[i]<=1000。
题目思路
前言
本来我以为是最短路什么的。。。结果是我太菜,个人认为此题还是补充了自己知识,学到了不少
知识
树的直径表示最长的那段路径,显然可以任意点进行dfs求这一点到任意一点的最长距离,则那个点为直径的一个端点,然后在端点dfs找出最长距离,另一个点就是直径的另外一个端点。
正文
其实最后就三次dfs解决问题
代码
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=5e4+5;
int n,a[maxn],cnt,head[maxn],u,v,pos[maxn],x,y,ans;
struct node{
int to,next;
}e[maxn<<1];
void add(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int son,int fa,int cnt){//儿子,父亲,要走多少步
pos[son]=max(pos[son],cnt);
for(int i=head[son];i;i=e[i].next){
if(e[i].to!=fa){
dfs(e[i].to,son,cnt+1);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n-1;i++){
cin>>u>>v;
add(u,v),add(v,u);
}
dfs(1,0,0);//以1开始dfs找直径的一个端点
int mi=-1;
for(int i=1;i<=n;i++){//x为直径的一个端点
if(pos[i]>mi){
mi=pos[i];
x=i;
}
}
memset(pos,0,sizeof(pos));//清空
dfs(x,0,0);
mi=-1;
for(int i=1;i<=n;i++){//y为直径的另一个端点
if(pos[i]>mi){
mi=pos[i];
y=i;
}
}
dfs(y,0,0);//找y到其他的距离和x到其他点的距离的最大值
for(int i=1;i<=n;i++){
ans=max(ans,pos[i]*a[i]);
}
cout<<ans<<'\n';
return 0;
}