很有意思的题目
虽然说被我写的特别长
要做的事情就是先找到最大的点，然后找到与这个点相连的点中最大的那个
之后显然被选择的点只能在这两个中左右横跳。
有意思的是，这个写法并不需要特判n==1
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
int zn[10000001];
int Aimee;
int Dr;
int n,m;
int t;
int x,y;
int f;
int head[10000001];
struct b{
int to;
int ne;
}ed[19000001];
int ans;
int p;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void add(int f,int to){
p++;
ed[p].ne=head[f];
ed[p].to=to;
head[f]=p;
return ;
}
int deal(){
int cnt=8000001;
int len=0;
for(int i=head[Dr];i;i=ed[i].ne){
if(zn[ed[i].to]>len){
len=zn[ed[i].to];
cnt=ed[i].to;
}else{
if(zn[ed[i].to]==len){
if(cnt>ed[i].to){
cnt=ed[i].to;
}
}
}
}
return cnt;
}
int Archie;
int deall(){
int cnt=-1;
int len=0;
for(int i=head[Dr];i;i=ed[i].ne){
if(ed[i].to==Archie)
continue;
if(zn[ed[i].to]>len){
len=zn[ed[i].to];
cnt=ed[i].to;
}else{
if(zn[ed[i].to]==len){
if(cnt>ed[i].to){
cnt=ed[i].to;
}
}
}
}
return cnt;
}
void meaningless(){
int imp=(m-(Aimee-zn[Archie]));
if(Archie>Dr){
swap(Archie,Dr);
}
if((imp&1)){
cout<<Dr<<endl;
}else{
cout<<Archie<<endl;
}
return ;
}
signed main(){
int maxn=8000001;
t=read();
while(t--){
n=read();m=read();
p=0;
Aimee=0;
Archie=0;
for(int i=1;i<=n;++i){
zn[i]=read();
if(zn[i]>Aimee){
Aimee=zn[i];
Dr=i;
}
head[i]=0;
}
for(int i=1;i<n;++i){
x=read();y=read();
add(x,y);
add(y,x);
}
Archie=deal();
if(Archie==maxn){
cout<<Dr<<endl;
continue;
}
if(Aimee-zn[Archie]>m){
cout<<Dr<<endl;
continue;
}
if(Aimee-zn[Archie]==m){
cout<<min(Dr,Archie)<<endl;
continue;
}
meaningless();
}
return 0;
}