1 条题解

  • 0
    @ 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
    上传者