void vtbuild(int k){
P[++k]=1,sort(P+1,P+k+1,cmpd);
stk[ktp=1]=P[1];
for(int i=2;i<=k;i++){
if(P[i]==P[i-1])continue;int ca=getlca(P[i],stk[ktp]);
if(ca!=stk[ktp]){
while(dfn[ca]<dfn[stk[ktp-1]])addedge(stk[ktp-1],stk[ktp]),ktp--;
if(dfn[ca]!=dfn[stk[ktp-1]])addedge(ca,stk[ktp]),stk[ktp]=ca;
else addedge(ca,stk[ktp--]);
}
stk[++ktp]=P[i];
}
for(int i=1;i<ktp;i++)addedge(stk[i],stk[i+1]);
}
int main(){
for(int i=1;i<=M;i++){
readi(K);
for(int j=1;j<=K;j++)readi(P[j]),isk[P[j]]=1;
vtbuild(K);DP(1),writil(dp[1]);
for(int j=1;j<=K;j++)isk[P[j]]=0;
}
return 0;
}
发现哪里错了吗?
是的这个错误极为唐诗:我们人为往长为 k 的 P 数组最前面添了一个 1,但是 DP 完后在清空 isk
的时候却清的是 P 的前 k 个元素,这说明我们清漏了一个。
纯唐。