#include #define rep(i,n)for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pairP; class LCA{ public: vector>>E; vector>par; vectord1; vectord2; int MAX_LOG=18; int n; LCA(){} LCA(int N){ n=N; E=vector>>(n); par=vector>(MAX_LOG,vector(n)); d1=vector(n); d2=vector(n); } void add_edge(int a,int b,int c){ E[a].push_back(make_pair(c,b)); E[b].push_back(make_pair(c,a)); } void add_edge(int a,int b){ E[a].push_back(make_pair(1,b)); E[b].push_back(make_pair(1,a)); } private: void dfs(int u,int p,int a,long long b){ par[0][u]=p;d1[u]=a;d2[u]=b; for(auto&v:E[u]){ if(v.second!=p)dfs(v.second,u,a+1,b+v.first); } } bool flag=false; void init(){ dfs(0,-1,0,0); for(int i=1;id1[v])swap(u,v); for(int i=0;i>i&1)v=par[i][v]; } if(u==v)return u; for(int i=MAX_LOG-1;i>=0;i--){ if(par[i][u]!=par[i][v]){ u=par[i][u]; v=par[i][v]; } } return par[0][u]; } long long dist(int u,int v){ int l=lca(u,v); return d2[u]+d2[v]-d2[l]*2; } }; template class BIT{ public: vectorbit; T cnt; BIT(int n){ bit=vector(n+10); cnt=0; } void add(int k,T x){ k++; while(k<(int)bit.size()){ bit[k]+=x; k+=k&-k; } cnt+=x; } T sum(int k){ k++; T res=0; while(k){ res+=bit[k]; k-=k&-k; } return res; } T sum2(int k){ return cnt-sum(k); } }; LCA lca; int n,K; int c[200000]; ll d[200000]; int L[200000],R[200000];//lca from left,right int b[200000]; ll calc1(ll t){//score only ll ans=0; BITbit(K); vector

query; ll S=0; rep(i,K-2){ int dep=lca.d1[lca.lca(L[i],c[K-1])]; S+=d[i]; query.push_back(P(t-dep-S,b[i])); } S=0; rep(i,K-1){ S+=d[i]; if(S+lca.d1[L[i]]<=t)ans++; } sort(query.begin(),query.end()); vector

sum; ll s=0; for(int i=K-1;i>=0;i--){ s+=d[i]; sum.push_back(P(s,i)); } sort(sum.begin(),sum.end()); int g=0; for(auto p:query){ while(gbit(K); vectorquery; query.push_back({t,0,K}); ll S=0; rep(i,K-2){ S+=d[i]; query.push_back({t-S,i+2,b[i]}); } sort(query.begin(),query.end(),[](st a,st b){return a.asum; ll s=0; for(int i=K-1;i>=0;i--){ s+=d[i]; sum.push_back(P(s+lca.d1[R[i]],i)); } sort(sum.begin(),sum.end()); int g=0; for(auto p:query){ while(g>n>>K; lca=LCA(n); rep(i,K){ scanf("%d",&c[i]);c[i]--; } rep(i,K)scanf("%lld",&d[i]); rep(i,n-1){ int a,b;scanf("%d%d",&a,&b);a--;b--; lca.add_edge(a,b); } lca.lca(0,1); for(int i=K-1;i>=0;i--){ if(i==K-1)R[i]=c[i]; else R[i]=lca.lca(R[i+1],c[i]); } rep(i,K){ if(i==0)L[i]=c[i]; else L[i]=lca.lca(L[i-1],c[i]); } rep(i,K-2){ int ok=K-1,ng=i+1; int node=lca.lca(c[K-1],L[i]); while(ok-ng>1){ int t=(ok+ng)/2; if(lca.lca(L[i],R[t])==node)ok=t; else ng=t; } b[i]=ok; } ll E=K*(ll)(K+1)/2+1; //~ cout<<"E="<