题目:https://www.lydsy.com/JudgeOnline/problem.php?id=5072
发现对于每个子树,黑点个数确定时,连通块的大小取值范围一定是一段区间;所以考虑只最小化最小值、最大化最大值,记 f 和 g 简单dp即可。
注意可能从当前子树里选0个点!此时会用自己更新自己!!所以要先复制一份原来的用来更新!
快速回答询问,本可以记差分数组,每个子树算完后给合法部分区间赋值;但空间开不下。
于是绞尽脑汁,终于想出可以开 bool 数组分块来赋值!!然而WA得不行。
交流后发现那个“取值是一段区间”的性质,在全局也是适用的(很明显……)!所以只要更新一下合法的最值就行了……
然后对拍半天 bool 分块,发现因为有 0 的值,所以标号应该是 0~base-1 这样;而且代码里注释的那个部分是 < 和 >= 而不是 <= 和 >!
然后又因为数据生成出错而以为自己还是不对而又拍、查了半天;最后分块的方法虽然慢一点,但也A了。感觉很好!
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=5002,M=73;int T,n,q,base,hd[N],xnt,to[N<<1],nxt[N<<1],siz[N],f[N][N],g[N][N],tf[N],tg[N];bool b[N],ok[N][N],ok2[M][N];//siz,blackint rdn(){ int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3) (ret<<1) ch-'0',ch=getchar(); return fx?ret:-ret;}void add(int x,int y){ to[ xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt; to[ xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;}int calc(int x){return x/base 1;}//0~base-1void dfs(int cr,int fa){ f[cr][b[cr]]=g[cr][b[cr]]=1; siz[cr]=b[cr]; for(int i=hd[cr],v;i;i=nxt[i]) if((v=to[i])!=fa) { dfs(v,cr); memcpy(tf,f[cr],sizeof f[cr]); memcpy(tg,g[cr],sizeof g[cr]); for(int j=siz[cr] siz[v];j>=b[cr];j--) for(int k=max((int)b[v],j-siz[cr]);k<=siz[v]&&k<=j;k ) { f[cr][j]=min(f[cr][j],tf[j-k] f[v][k]); g[cr][j]=max(g[cr][j],tg[j-k] g[v][k]); } siz[cr] =siz[v]; } /* for(int i=0;i<=siz[cr];i ) f[0][i]=min(f[0][i],f[cr][i]), g[0][i]=max(g[0][i],g[cr][i]); */ for(int i=0;i<=siz[cr];i ) { if(f[cr][i]>g[cr][i])continue; int l=calc(f[cr][i]),r=calc(g[cr][i]); if(r-l<=1) { for(int j=f[cr][i];j<=g[cr][i];j ) ok[j][i]=1; } else { for(int j=l 1;j<r;j )ok2[j][i]=1; int lm=l*base; for(int j=f[cr][i];j<lm;j )ok[j][i]=1;//< lm=(r-1)*base; for(int j=g[cr][i];j>=lm;j--)ok[j][i]=1;//>= } }}int main(){ T=rdn(); while(T--) { n=rdn(); q=rdn(); base=sqrt(n); memset(hd,0,sizeof hd); xnt=0; memset(ok,0,sizeof ok); memset(ok2,0,sizeof ok2); for(int i=1,u,v;i<n;i ) { u=rdn(); v=rdn(); add(u,v); } for(int i=1;i<=n;i )b[i]=rdn(); memset(f,0x3f,sizeof f); memset(g,-2,sizeof g); dfs(1,0); for(int i=1,x,y,d;i<=q;i ) { x=rdn(); y=rdn(); d=calc(x); puts((ok[x][y]||ok2[d][y])?"YES":"NO"); //puts(x>=f[0][y]&&x<=g[0][y]?"YES":"NO"); } puts(""); } return 0;}
来源:http://www.icode9.com/content-4-60801.html
联系客服