Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
23899 岳亦铭 【BJ】T1 C++ 运行超时 70 1000 MS 24028 KB 1992 2023-12-03 20:50:24

Tests(14/20):


#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); } 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]); } f[u][1]+=a[u]; f[u][2]+=b[u]; f[u][3]+=b[u]; int tmp1=0,tmp2=-1e15; for(int i=0;i<edge[u].size();i++) { int v=edge[u][i]; if(v==fa) continue; int nxt1=tmp1,nxt2=tmp2; nxt1+=max(f[v][1],f[v][3]); nxt2+=max(f[v][0],max(f[v][1],f[v][3])); nxt2=max(nxt2,tmp1+f[v][0]); tmp1=nxt1,tmp2=nxt2; } f[u][3]+=tmp2; } 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; }


测评信息: