https://ac.nowcoder.com/acm/contest/94879/F
考虑不用传送，除了进入第一个节点，其他不管所有节点杀死一个怪物代价都是3。
所以$ans = min(n,1+(x-1)/3)$
考虑每个传送，只需要考虑1到u到v到1的体力消耗和价值，如果体力足够的话，剩下的答案仍然是:剩余体力/3。如果体力不够的话就不需要考虑这个传送了。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

vector<vector<int>> fa;
vector<int> dep;
vector<vector<int>> g;
void initlca(int x){
    for(int i=0;i<=20;i++) fa[x][i+1] = fa[fa[x][i]][i];
    for(auto y:g[x]){
        if(y==fa[x][0]) continue;
        dep[y] = dep[x]+1;
        fa[y][0] = x;
        initlca(y);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int d=dep[x]-dep[y],i=0;d;d>>=1,i++){
        if(d&1) x = fa[x][i];
    }
    if(x==y) return x;
    for(int i=20;i>=0;i--){
        if(fa[x][i]!=fa[y][i]) x  = fa[x][i],y = fa[y][i];
    }
    return fa[x][0];
}
void solve(){
    int n,x;
    cin>>n>>x;
    g = vector<vector<int>>(n+1);
    fa = vector<vector<int>>(n+1,vector<int>(25));
    dep = vector<int>(n+1,0);
    vector<int> a(n+1);
    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);
    }
    initlca(1);
    int ans = min(n,1+(x-1)/3);
    for(int i=1;i<=n;i++){
        if(i==a[i]) continue;
        int must = dep[i]+dep[a[i]]+1;
        int res = dep[i]+dep[a[i]] - dep[lca(i,a[i])] + 1;
        must += res;
        if(x >= must) ans = max(ans,res+min(n-res,(x-must)/3));
    }
    cout<<ans<<endl;
}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}