Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
23900 | 岳亦铭 | 【BJ】T1 | C++ | 运行超时 | 70 | 1000 MS | 31776 KB | 1760 | 2023-12-03 20:53:50 |
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=1e5+10; int n,q,k,L; int a[maxn],b[maxn]; vector<int> edge[maxn],vec[maxn]; int dep[maxn]; int f[maxn][10]; int sum[maxn]; void dfs(int u,int fa) { for(int i=0;i<edge[u].size();i++) { int v=edge[u][i]; if(v==fa) continue; dep[v]=dep[u]+1; dfs(v,u); } } void dp(int u,int fa) { for(int i=0;i<edge[u].size();i++) { int v=edge[u][i]; if(v==fa) continue; dp(v,u); } int minn=1e15; for(int i=0;i<edge[u].size();i++) { int v=edge[u][i]; if(v==fa) continue; f[u][0]+=max(max(f[v][0],f[v][1]),max(f[v][2],f[v][3])); f[u][1]+=max(max(f[v][0],f[v][1]),f[v][3]); f[u][2]+=max(max(f[v][0],f[v][1]),f[v][3]); minn=min(minn,max(max(f[v][0],f[v][1]),f[v][3])-f[v][0]); } f[u][3]=f[u][2]-minn; f[u][1]+=a[u]; f[u][2]+=b[u]; f[u][3]+=b[u]; } int ans[maxn]; signed main() { ios::sync_with_stdio(false); cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; cin>>k; int u,v; for(int i=1;i<n;i++) { cin>>u>>v; edge[u].push_back(v); edge[v].push_back(u); } dfs(k,0); dp(k,0); for(int i=1;i<=n;i++) vec[dep[i]].push_back(i); for(int i=0;i<=n;i++) { int t=0; for(int j=0;j<vec[i].size();j++) { int u=vec[i][j]; t+=max(a[u],b[u]); ans[i]+=max(max(f[u][0],f[u][1]),max(f[u][2],f[u][3])); } if(i==0) sum[i]=t; else sum[i]=sum[i-1]+t; if(i!=0) ans[i]+=sum[i-1]; } while(q--) { cin>>L; cout<<ans[L]<<"\n"; } return 0; }