洛谷P4426 毒瘤 [HNOI/AHOI2018] 虚树+树上dp
正解:虚树+树上dp
解题报告:
传送门!
首先解释一下题意趴,,,语文70pts选手已经开始看不懂题辣QAQ
大概就是个给一个图,求独立集方案,且保证图是联通的,边的数量最多只比点多10
首先思考如果边的数量=点的数量-1,也就是一棵树的时候怎么搞?
直接树上dp就好,f[i][0/1]:选/不选第i个点方案数,转移就f[i][0]=∏(f[son][0]+f[son][1]),f[i][1]=∏f[son][0]
然后考虑多的边怎么搞呢
从上面那个思路自然而然地可以考虑到,可以暴力枚举非树边的情况,然后一个个计算
这样就有80pts辣!
然后考虑怎么继续优化呢
思考之前我想先问个问题吼
想到这一步有麻油想到辣NOIp2018D2T3保卫王国昂,,,一样是强制几个点选/不选,一样是树上dp,转移方程有一部分区别但差别并不大
所以这里也可以用保卫王国的两个方法做了这题!
第一个!树上倍增+树上dp+虚树
首先可以想到,其实虚树上的状态是不会影响其他节点的dp值的(显然,感性理解即可
所以只用枚举状态在虚树上做树形dp就好
这样就从O(211n)变成辣O(211*11+n)!就过去辣!
具体说下怎么在虚树上做dp
设x是y在虚树上的儿子节点,t是y在实树上的儿子节点
显然存在f[t][0]=k1[x][0]*f[x][0]+k2[x][0]*f[x][1],f[t][1]=k1[x][1]*f[x][0]+k2[x][1]*f[x][1]
所以现在发现只要能把dp系数k求出来,然后一直这么拆下去(就是把x的f什么的也表示出来)就能在每次枚举状态之后O(1)地算出来辣
然后说下怎么求dp系数k呢
对于一条虚树边(u,v),将原树中u到v的路径提出来,从v节点向上跳并暴力转移系数,若遇到分叉则额外转移上分叉处的系数.
由于虚树的性质可以知道分叉的子树内不存在关键点(否则分叉处会作为lca出现在虚树上),因此分叉处的系数可以暴力转移.
然后在6天之后我总算把代码打出来了,,,QAQ
有几个要注意的点,分别港下QAQ
1) 这道题需要记录每条边是否是连接两个两个不可共存的点的,就是要开个bool数组存下来嘛
然后这种是有个小技巧的.就是如果是lsqxx存储的话,显然连接相同两个点的两条边是相邻的
所以直接vis[i]=vis[i^1]=1
但是这里要注意一下,,,如果是这样儿的话ed_cnt要从1开始QAQ
其实应该是所有人都知道的注意点?然而我是第一次用这个所以不知道还调了半天QAQ
2) 这个是比较容易想到的,只是我忽略了所以记录下QAQ
就是在枚举状态的时候,也是要开个bool数组记录某个节点是否强制选/不选嘛
然后这里的话代码不应该是,exi[i]=1
应该是exi[land[i]]=1
另外那个状态是要从2<<1开始,不是2<<0
因为点的编号是从1开始的,从2<<1开始的话就不要做一些杂七杂八的细节辣QAQ
好像麻油了,然后这题细节真的贼多,,,我调了一个下午,,,wsl,,,麻油脑子了QAQ
这儿是代码QAQ然后因为我把变量名混淆了,,,所以下面打了注释记录各个变量的意义QAQ#include<bits/stdc++.h> using namespace std; #define il inline #define ll long long #define rg register #define gc getchar() #define mp make_pair #define t_rl(i) edge_rl[i].to #define t_fk(i) edge_fk[i].to #define w_rl(i) edge_rl[i].wei #define w_fk(i) edge_fk[i].wei #define rp(i,x,y) for(rg ll i=x;i<=y;++i) #define my(i,x,y) for(rg ll i=x;i>=y;--i) #define e_rl(i,x) for(rg ll i=head_rl[x];i;i=edge_rl[i].nxt) #define e_fk(i,x) for(rg ll i=head_fk[x];i;i=edge_fk[i].nxt) #define fd_fa(i,x,y) for(rg ll i=x;fa[i][0]!=y;i=fa[i][0]) const ll N=100000+100,inf=1e12,mod=998244353; ll edge_rl_cnt=1,edge_fk_cnt=1,head_rl[N],head_fk[N],dep[N],fa[N][20],n,m,ld_cnt,land[N],cnt_dfn,dfn[N],stck[N],head_stck,as,fk_num,g[N][2],f[N][2],k0[N][2],k1[N][2],poww[N],exi[N]; bool isfked[N<<1],infk[N]; struct ed{ll to,nxt;}edge_rl[N<<1],edge_fk[N<<1]; struct fked{ll fr,to;}fk[N]; il ll read() { rg char ch=gc;rg ll x=0;rg bool y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il void ad_rl(rg ll x,rg ll y){edge_rl[++edge_rl_cnt]=(ed){y,head_rl[x]};head_rl[x]=edge_rl_cnt;} il void ad_fk(rg ll x,rg ll y){edge_fk[++edge_fk_cnt]=(ed){y,head_fk[x]};head_fk[x]=edge_fk_cnt;infk[x]=1;infk[y]=1;} void dfs_rl(ll nw,ll fat) { dfn[nw]=++cnt_dfn; dep[nw]=dep[fat]+1;fa[nw][0]=fat;rp(i,1,19)fa[nw][i]=fa[fa[nw][i-1]][i-1]; e_rl(i,nw) { if(t_rl(i)^fat) { if(dfn[t_rl(i)])fk[++fk_num]=(fked){nw,t_rl(i)},isfked[i]=isfked[i^1]=1; else dfs_rl(t_rl(i),nw); } } } il bool cmp(ll gd,ll gs){return dfn[gd]<dfn[gs];} il ll lca(ll x,ll y) { if(dep[x]<dep[y])swap(x,y); my(i,19,0)if(dep[fa[x][i]]>=dep[y])x=fa[x][i]; if(x==y)return x; my(i,19,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } il void build_fk() { rp(i,1,fk_num){if(!infk[fk[i].fr])infk[fk[i].fr]=1,land[++ld_cnt]=fk[i].fr;if(!infk[fk[i].to])infk[fk[i].to]=1,land[++ld_cnt]=fk[i].to;} head_stck=edge_fk_cnt=0;sort(land+1,land+1+ld_cnt,cmp);if(!infk[1])infk[1]=1,stck[++head_stck]=1; rp(i,1,ld_cnt) { if(!head_stck)stck[++head_stck]=land[i]; else { ll grd=lca(stck[head_stck],land[i]); if(grd==stck[head_stck]){stck[++head_stck]=land[i];continue;} while(dep[stck[head_stck-1]]>dep[grd])ad_fk(stck[head_stck-1],stck[head_stck]),--head_stck; if(grd!=stck[head_stck-1])ad_fk(grd,stck[head_stck]),stck[head_stck]=grd,stck[++head_stck]=land[i]; else ad_fk(grd,stck[head_stck]),stck[head_stck]=land[i]; } } while(head_stck>1)ad_fk(stck[head_stck-1],stck[head_stck]),--head_stck; } il void predp(ll x,ll no) { f[x][0]=f[x][1]=1,infk[x]=1; e_rl(i,x) { if(t_rl(i)==fa[x][0] || t_rl(i)==no || infk[t_rl(i)] || isfked[i])continue; predp(t_rl(i),no); f[x][0]=1ll*f[x][0]*(f[t_rl(i)][0]+f[t_rl(i)][1])%mod; f[x][1]=1ll*f[x][1]*f[t_rl(i)][0]%mod; } } il void gtk(ll x,ll y) { k0[x][0]=1,k1[x][1]=1; fd_fa(i,x,y) { predp(fa[i][0],i); ll t0=k0[x][0],t1=k1[x][0],t3=k0[x][1],t4=k1[x][1],fat=fa[i][0]; k0[x][0]=1ll*f[fat][0]*(t0+t3)%mod; k1[x][0]=1ll*f[fat][0]*(t1+t4)%mod; k0[x][1]=1ll*f[fat][1]*t0%mod; k1[x][1]=1ll*f[fat][1]*t1%mod; } } il void prewk(ll x) { e_fk(i,x)prewk(t_fk(i)),gtk(t_fk(i),x); f[x][0]=f[x][1]=1; e_rl(i,x) { if(infk[t_rl(i)] || isfked[i] || t_rl(i)==fa[x][0])continue; predp(t_rl(i),0); f[x][0]=1ll*f[x][0]*(f[t_rl(i)][0]+f[t_rl(i)][1])%mod; f[x][1]=1ll*f[x][1]*f[t_rl(i)][0]%mod; } } il void dp(ll x) { g[x][0]=f[x][0];g[x][1]=f[x][1]; e_fk(i,x) { ll to=t_fk(i);dp(to); ll f0=(1ll*k0[to][0]*g[to][0]%mod+1ll*k1[to][0]*g[to][1]%mod)%mod; ll f1=(1ll*k0[to][1]*g[to][0]%mod+1ll*k1[to][1]*g[to][1]%mod)%mod; g[x][0]=1ll*g[x][0]*(f0+f1)%mod,g[x][1]=1ll*g[x][1]*f0%mod; } if(exi[x]==1)g[x][0]=0;if(exi[x]==-1)g[x][1]=0; } int main() { freopen("dl.in","r",stdin);freopen("dl.out","w",stdout); n=read();m=read(); rp(i,1,m){ll x=read(),y=read();ad_rl(x,y);ad_rl(y,x);} dfs_rl(1,0);build_fk();poww[1]=1;rp(i,2,ld_cnt+1)poww[i]=poww[i-1]<<1; prewk(1); rp(i,0,poww[ld_cnt+1]-1) { rp(j,1,ld_cnt)if(i&poww[j])exi[land[j]]=1;else exi[land[j]]=-1; bool flg=0; rp(j,1,fk_num)if(exi[fk[j].fr]==1 && exi[fk[j].to]==1){flg=1;break;} if(flg)continue; dp(1);as=(as+(g[1][0]+g[1][1])%mod)%mod; } printf("%lld\n",as); return 0; } /* 依然mk一下取名 g[][]:实际dp的as f[][]:不考虑虚树balabala的dp的as k0[][]:dp的系数,不选 k1[][]:同上,选 f0:不选 f1:选 注:k[0/1][][0/1]前一个表虚树上点选不选,后一个表示我选不选 */ /* wsl变量太多了,我重新理一下QAQ edge_rl_cnt:原树的边数 edge_fk_cnt:虚树的边数 head_rl[N]:原树lsqxx head_fk[M]:虚树lsqxx dep[N]:原树深度,lca中用 fa[M][20]:倍增,lca中用,之后有要跳到父亲的环节要用 n:树的点对数量 m:边的数量 ld_cnt:不能共存的点的数量 land[M]:不能共存的点对 cnt_dfn:dfn的数量 dfn[N]:dfn序,建虚树排序时用 stck[N]:建虚树时用 head_stck:建虚树时用,栈头指针 as:就是ans,最后求各个状态时乘起来输出 fk_num:不能共存的点对数量 g[N][2],f[N][2],k0[N][2],k1[N][2]:见上,已整理好了 poww[M]:预处理1<<i,方便之后的运算 exi[M]:不能共存的点i是否存在 isfked[N<<1]:原树上的边484连接不能共存的点的 infk[N]:原树上的边484在虚树上?忘了等下写,,, struct ed{ll to,nxt;}edge_rl[N<<1],edge_fk[M]:原树上的边和虚树上的边 struct fked{ll fr,to;}fk[N]:不能共存的点对 */
第二个!矩阵快速幂预处理!
首先在之前做dp的学习总结中说到优化的时候其实就提到辣
因为dp是一个转移式,也就是个线性递推式,所以我们可以考虑把它变成一个矩阵的形式
然后用一些什么线段树平衡树之类的毒瘤神仙玩意儿维护一下
这个方法是比较正统的,动态dp的做法QwQ
所以显然我还麻油很好的落实只是知道有这么个东西辣
所以代码咕辣QAQ