❤Aimee❤

很有意思的题目

虽然说被我写的特别长

要做的事情就是先找到最大的点，然后找到与这个点相连的点中最大的那个

之后显然被选择的点只能在这两个中左右横跳。

有意思的是，这个写法并不需要特判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;
}