提交时间:2023-12-02 19:50:51
运行 ID: 23887
//70pts #include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e5+10; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,q,K,w1[maxn],w2[maxn],RT,dep[maxn]; vector<int>v[maxn],P[maxn]; ll dp[maxn][3][2],RES[maxn]; void dfs(int u,int fa){ for(int x:v[u]){ if(x==fa)continue; dep[x]=dep[u]+1;dfs(x,u); } }void dfs2(int u,int fa){ dp[u][0][0]=w1[u],dp[u][2][0]=0,dp[u][1][0]=-1e18,dp[u][1][1]=w2[u]; //if(dep[u]<=K)dp[u][1][0]=w2[u]; for(int x:v[u]){ if(x==fa)continue; dfs2(x,u); dp[u][0][0]+=max(dp[x][1][0],max(dp[x][2][0],dp[x][0][0])); dp[u][2][0]+=max(dp[x][0][0],max(dp[x][1][0],max(dp[x][1][1],dp[x][2][0]))); dp[u][1][0]=max(dp[u][1][0]+max(dp[x][0][0],max(dp[x][1][0],dp[x][2][0])),dp[u][1][1]+dp[x][2][0]); dp[u][1][1]+=max(dp[x][0][0],max(dp[x][1][0],dp[x][2][0])); } } void slv(){ n=read(),q=read(); up(i,1,n)w1[i]=read();up(i,1,n)w2[i]=read(); RT=read(); up(i,1,n-1){ int x=read(),y=read(); v[x].p_b(y),v[y].p_b(x); }dfs(RT,0); up(i,1,n)P[dep[i]].p_b(i); dfs2(RT,0); ll sm=0; up(i,0,n){ if(i){ for(int x:P[i-1])sm+=max(w1[x],w2[x]); }ll res=sm; for(int x:P[i])res+=max(dp[x][0][0],max(max(dp[x][1][0],dp[x][1][1]),dp[x][2][0])); RES[i]=res; } while(q--){ K=read();cout<<RES[K]<<'\n'; } }int main(){ //freopen("tree.in","r",stdin); //freopen("tree.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }