比赛 |
20160415x |
评测结果 |
AWAWWWWWWW |
题目名称 |
游戏内测 |
最终得分 |
20 |
用户昵称 |
咸鱼二号 |
运行时间 |
2.341 s |
代码语言 |
C++ |
内存使用 |
15.57 MiB |
提交时间 |
2016-04-15 15:35:45 |
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<cstdlib>
#include<iomanip> //cout<<setiosflags(ios::fixed)<<setprecision(2);
#include<ctime> //double a=(double)clock(); cout<<a<<endl;
#include<vector>
#include<queue>
using namespace std;
const int maxn=500010;
inline int read(){
int x=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1; ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return ff*x;
}
int N,lin[maxn],len=0,C[maxn];
struct edge{
int y,next;
}e[maxn<<1];
inline void insert(int xx,int yy){
e[++len].next=lin[xx];
lin[xx]=len;
e[len].y=yy;
}
inline void ins(int xx,int yy)
{insert(xx,yy),insert(yy,xx);}
int q[maxn],head,tail,dis[maxn];
void bfs(){
head=tail=0;
q[head]=1;
for(;head<=tail;head++){
for(int i=lin[q[head]];i;i=e[i].next)
if(!dis[e[i].y]){
dis[e[i].y]=dis[q[head]]+1;
q[++tail]=e[i].y;
}
}
}
int ans=0;
int main(){
freopen("gamebeta.in","r",stdin);
freopen("gamebeta.out","w",stdout);
N=read();
for(int i=1;i<=N;i++)
C[i]=read();
for(int i=1;i<N;i++)
ins(read(),read());
bfs();
for(int i=1;i<=N;i++)
if(dis[i]+C[i]>ans)
ans=dis[i]+C[i];
printf("%d\n",ans);
return 0;
}