1 条题解
-
0陆霆轩 (lutingxuan) LV 10 MOD @ 2024-10-6 18:30:37
#include<bits/stdc++.h> #define inl inline using namespace std; typedef long long ll; const int N=1e5+5,IB=1<<21; char IN[IB],*IS=IN+IB,*IT=IS; #define getchar() (IS==IT&&(fread(IS=IN,1,IB,stdin)),*IS++) int n,m,rt; ll a[N],b[N],f[N][2],g[N],an[N]; vector<int> e[N],s[N]; inl int Read() { int s=0; char c; while(!isdigit(c=getchar())); for(;isdigit(c);c=getchar()) s=s*10+c-'0'; return s; } inl void DP(int p,int fr,int d) { s[d].push_back(p); g[p]=-LLONG_MAX; for(int v:e[p]) if(v!=fr) { DP(v,p,d+1); ll t=max(f[v][0],f[v][1]+max(a[v],b[v]+g[v])); f[p][0]+=max(t,f[v][1]+b[v]); f[p][1]+=t; g[p]=max(g[p],f[v][0]-t); } } int main() { n=Read(); m=Read(); for(int i=1;i<=n;++i) a[i]=Read(); for(int i=1;i<=n;++i) b[i]=max(a[i],1ll*Read()); rt=Read(); for(int x,y,i=n;--i;) e[x=Read()].push_back(y=Read()), e[y].push_back(x); DP(rt,0,0); for(int i=0;i<=n;++i) { an[i+1]=an[i]; for(int v:s[i]) an[i]+=max(f[v][0],f[v][1]+b[v]), an[i+1]+=b[v]; } while(m--) printf("%lld\n",an[Read()]); return 0; }
- 1
信息
- ID
- 3215
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 9
- 已通过
- 1
- 上传者