Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
23892 | 岳亦铭 | 【BJ】T1 | C++ | 运行超时 | 70 | 1000 MS | 12888 KB | 1887 | 2023-12-03 19:36:48 |
#include<bits/stdc++.h> using namespace std; #define int long long const int MAXN=200010,base=131,Mod=998244353; int n,q,k,L,ans,dp[MAXN][4],vis[MAXN]; struct place{ int m,w,sd; }p[MAXN]; struct Edge{ int v,nx; }edge[MAXN]; int h[MAXN],CNT; void init(){ memset(h,-1,sizeof(h));CNT=0; } void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} void f(int x,int lst,int tp){ int tmp=0;dp[x][3]=1e18;dp[x][0]=dp[x][1]=dp[x][2]=0; for(int i=h[x];i!=-1;i=edge[i].nx){ int v=edge[i].v; if(edge[i].v==lst)continue; f(edge[i].v,x,tp-1); dp[x][0]+=max(max(dp[v][0],dp[v][1]),max(dp[v][2],dp[v][3])); dp[x][1]+=max(dp[v][0],max(dp[v][1],dp[v][3])); dp[x][2]+=max(dp[v][0],max(dp[v][1],dp[v][3])); dp[x][3]=min(max(dp[v][0],max(dp[v][1],dp[v][3]))-dp[v][0],dp[x][3]); tmp+=max(dp[v][0],max(dp[v][1],dp[v][3])); } if(dp[x][3]==1e18)dp[x][3]=-1; if(dp[x][3]!=-1)dp[x][3]=tmp-dp[x][3]; dp[x][1]+=p[x].m; dp[x][2]+=p[x].w; if(dp[x][3]!=-1)dp[x][3]+=p[x].w; else dp[x][3]=p[x].m; if(tp>0)dp[x][2]=dp[x][3]=dp[x][2]; return; } signed main(){ init(); scanf("%lld%lld",&n,&q); for(int i=1;i<=n;i++){ scanf("%lld",&p[i].m); } for(int i=1;i<=n;i++){ scanf("%lld",&p[i].w);p[i].w=max(p[i].w,p[i].m); } scanf("%lld",&k); for(int i=1;i<n;i++){ int u,v; scanf("%lld%lld",&u,&v); add_side(u,v); } while(q--){ scanf("%lld",&L); f(k,-1,L+1);/* for(int i=1;i<=n;i++){ cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<" "<<dp[i][3]<<endl; }*/ printf("%lld\n",max(max(dp[k][0],dp[k][1]),max(dp[k][2],dp[k][3]))); } fclose(stdin); fclose(stdout); return 0; }