Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
27019 | LYLAKIOI | 【BJ】T3 | C++ | 运行出错 | 0 | 5 MS | 3276 KB | 2251 | 2024-02-29 19:20:46 |
#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p1 first #define p2 second #define p_b push_back using namespace std; typedef __int128 ll; const int maxn=1005; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,siz[maxn]; ll L,R,a[maxn]; vector<int>v[maxn]; vector<ll>dp[maxn][60],tmp[60]; void reduce(vector<ll>& vec){ sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end()); if(vec.empty())return; vector<ll>res; int i=0,j=0; while(i<int(vec.size())){ while(j<int(vec.size())&&vec[j]-vec[i]<=R-L)j++; j--; if(i!=j)res.p_b(vec[i]),res.p_b(vec[j]); else res.p_b(vec[i]); i=j+1; }vec=res; } bool vis; void dfs(int u,int fa){ if(u==2)vis=1; dp[u][1].p_b(a[u]);siz[u]=1; for(int x:v[u])if(x!=fa){ dfs(x,u); up(i,1,m+1)tmp[i].clear(); up(i,1,min(m+1,siz[u]))up(j,1,min(m+1,siz[x])){ if(i+j-1>m+1)break; if(i+j-1<=m+1){ for(ll xx:dp[u][i])for(ll yy:dp[x][j])tmp[i+j-1].p_b(xx+yy); } if(i+j<=m+1){ for(ll xx:dp[u][i])for(ll yy:dp[x][j])if(yy>=L&&yy<=R)tmp[i+j].p_b(xx); } } up(i,1,m+1)dp[u][i]=tmp[i],reduce(dp[u][i]); siz[u]+=siz[x]; } /*cout<<"Test "<<u<<' '<<siz[u]<<'\n'; up(i,1,m+1){ for(ll x:dp[u][i])cout<<x<<' '; cout<<'\n'; }cout<<'\n';*/ } void slv(){ n=read(),m=read(),L=read(),R=read(); up(i,1,n){ a[i]=read(); } up(i,1,n-1){ int x=read(),y=read(); v[x].p_b(y),v[y].p_b(x); }dfs(1,0); up(i,0,m){ auto it=lower_bound(dp[1][i+1].begin(),dp[1][i+1].end(),L); if(it!=dp[1][i+1].end()&&(*it)<=R)printf("1"); else printf("0"); }assert(vis); }int main(){ // freopen("large.in","r",stdin); // freopen("large.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }