提交时间:2023-12-02 19:46:43

运行 ID: 23881

#include<bits/stdc++.h> using namespace std; #define int long long #define endl "\n" int n,q,k; int a[200030]; int w[200300]; int f[200300][4]; int dep[200300]; //0:normal party //1:no party //2:big party,but not yet //3:big party vector<int>g[200300]; inline void dfs(int u,int fa){ f[u][0]=a[u]; f[u][2]=w[u]; f[u][3]=-1e18; for(int v:g[u]) if(v!=fa){ dep[v]=dep[u]+1; dfs(v,u); f[u][0]+=max(f[v][0],max(f[v][1],f[v][3])); f[u][1]+=max(f[v][0],max(f[v][1],max(f[v][2],f[v][3]))); f[u][3]=max(f[u][3]+max(f[v][0],max(f[v][1],f[v][3])),f[u][2]+f[v][1]); f[u][2]+=max(f[v][0],f[v][3]); } } int ANS[200300]; int EX[200300]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); cin>>n>>q; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>w[i]; cin>>k; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(k,0); for(int i=1;i<=n;i++) ANS[dep[i]]+=max(w[i],a[i]); for(int i=1;i<=n;i++) ANS[i]+=ANS[i-1]; for(int i=1;i<=n;i++){ int mx=0; for(int j=0;j<4;j++) mx=max(mx,f[i][j]); EX[dep[i]]+=mx; } while(q--){ int L; cin>>L; int res=0; if(L)res=ANS[L-1]; cout<<res+EX[L]<<endl; } cout.flush(); return 0; }