Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
23890 岳亦铭 【BJ】T1 C++ 解答错误 30 1000 MS 12896 KB 1845 2023-12-03 19:34:20

Tests(6/20):


#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]+=dp[v][2]; 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; }


测评信息: