#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=22; 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 Segtree{ int n; vectordat; T INIT; T E; functionF; public: Segtree(int n_,T INIT,T E,functionF):INIT(INIT),E(E),F(F){ n=1;while(n(2*n,INIT); } void set(int k,T x){ k+=n; dat[k]=x; while(k>1){ k>>=1; dat[k]=F(dat[k<<1],dat[(k<<1)+1]); } } void update(int k,T x){ k+=n; dat[k]=F(dat[k],x); while(k>1){ k>>=1; dat[k]=F(dat[k<<1],dat[(k<<1)+1]); } } T query(int l,int r){ T resl=E,resr=E; for(l+=n,r+=n;l>=1,r>>=1){ if(l&1)resl=F(resl,dat[l++]); if(r&1)resr=F(dat[--r],resr); } return F(resl,resr); } }; 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; Segtreeseg(K,0,0,[](int a,int b){return a+b;}); 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(gseg(K,0,0,[](int a,int b){return a+b;}); 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+2; cout<<"E="<