动态规划题单4

51天前发布

91.[ARC114F] Permutation Division

Bob 的策略一定是按照开头从大到小排。
所以最后的答案一定不小于原来的排列。

所以我们要使得最后的排列 \(Q\) 和原排列 \(P\) 的 LCP 尽可能长。
也就是说最后分段的形式满足：(\(t_i\) 是每一段的开头)

\(p_1=p_{t_1} > p_{t_2} > … > p_{t_m}\)。
不然的话，Bob 可以把后面的放到前面去。
这些段就是 LCP 长度。
\(p_{t_{m+1}},p_{t_{m+2}},…,p_{t_k} < p_{t_m}\)。
此时 Bob 会把 \(p_{t_{m+1}},p_{t_{m+2}},…,p_{t_k}\) 的 max 作为 \(q_{t_{m+1}}\)。

考虑二分 LCP 的长度 \(len\)，枚举 \(m\)，对于每个 \(m\) 我肯定是求出 \(p_{t_m}\) 的最大值，这样后面的段的选择会变多，设 \([len+1,n]\) 有 \(y\) 个数 < \(p_{t_m}\) 那么，如果 \(y+m\ge k\) 就是可行的，而 \(p_{t_{m+1}},p_{t_{m+2}},…,p_{t_k}\) 一定是选择最小的那几个。
于是问题变成求长度为 \(m\) 的下降子序列的末尾的最大值，这可以用 \(O(n\log n)\) 的 DP 来实现。

code

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second 
using namespace std;
const int N=2e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,k,a[N],b[N],pos[N],g[N],d,cnt[N],t[N];
bool flag[N];
int check(int mid){  //返回最大的 m 
	if(mid==0) return 0;
	for(int i=1;i<=n;i++) g[i]=0;
	g[1]=-a[1],d=1;  //取 - 变成求最长上升子序列 
	for(int i=2;i<=mid;i++){
		int l=upper_bound(g+1,g+d+1,-a[i])-g;
		if(l==1) continue;
		g[l]=-a[i];
		d=max(d,l);
	}
	for(int i=1;i<=n;i++) cnt[i]=0;
	for(int i=mid+1;i<=n;i++) cnt[a[i]]++; 
	for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];  //cnt[i] 几位 [len+1,n] 中小于 i 的个数
	for(int m=d;m>=1;m--){
		if(m+cnt[-g[m]]>=k) return m;
	} 
	return 0;   
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i],pos[a[i]]=i;
	int l=1,r=n,mid,len=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)) len=mid,l=mid+1;
		else r=mid-1;
	} 
	int m=min(k,check(len));
	
	sort(b+len+1,b+n+1); 
	for(int i=len+1,j=1;j<=k-m;i++,j++) t[j]=pos[b[i]],flag[t[j]]=true;
	for(int i=1;i<=len;i++) printf("%d ",a[i]);
	for(int i=k-m;i>=1;i--){  //注意 Bob 对于后面那几段是从大到小放的 
		for(int j=t[i];j<=n&&(j==t[i] || !flag[j]);j++){
			printf("%d ",a[j]);
		}
	}
	puts("");
	return 0;
}

92.[SDOI2011] 消耗战

虚树上 dp 的裸题。

我们称那些有资源的点为关键点

首先这题单次询问有个 \(O(n)\) 的树形 DP。
即设 \(f_u\) 表示 \(u\) 号点与其子树中的所有关键点不连通的最小代价，那么枚举儿子 \(v\)：

\(v\) 不是关键点：\(f_u += \min(f_v,w(u,v))\)。
\(v\) 是关键点：\(f_u += w(u,v)\)。

然后对所有关键点建出虚树在虚树上做这个 DP 就可以了。（应该不会有人看到 \(92\) 题了还不会虚树吧。）

code

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define fi first
#define se second 
using namespace std;
const int N=2.5e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,T,tot,head[N],to[N<<1],val[N<<1],Next[N<<1];
void add(int u,int v,int w){
	to[++tot]=v,val[tot]=w,Next[tot]=head[u],head[u]=tot;
}
int dfn[N],dep[N],fa[N][25],ming[N][25],num;
void dfs(int u){
	dfn[u]=++num;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i],w=val[i];
		if(v==fa[u][0]) continue;
		fa[v][0]=u,ming[v][0]=w;
		dep[v]=dep[u]+1;
		dfs(v);
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int t=20;t>=0;t--)
		if(dep[fa[x][t]]>=dep[y]) x=fa[x][t];
	if(x==y) return x;
	for(int t=20;t>=0;t--)
		if(fa[x][t] != fa[y][t]) x=fa[x][t],y=fa[y][t];
	return fa[x][0]; 
}
int ask(int x,int y){
	int Min=LLONG_MAX;
	if(dep[x]<dep[y]) swap(x,y);
	for(int t=20;t>=0;t--)
		if(dep[fa[x][t]]>=dep[y]) Min=min(Min,ming[x][t]),x=fa[x][t];
	if(x==y) return Min;
	for(int t=20;t>=0;t--)
		if(fa[x][t] != fa[y][t]) Min=min({Min,ming[x][t],ming[y][t]}),x=fa[x][t],y=fa[y][t];
	return min({Min,ming[x][0],ming[y][0]}); 	
}
int k,a[N],t[N],cnt;
bool flag[N];
vector<PII> G[N];
void Build_Virtual_Tree(){
	sort(a+1,a+k+1,[&](int x,int y){return dfn[x]<dfn[y];});
	cnt=0;
	t[++cnt]=1,t[++cnt]=a[k];
	for(int i=1;i<k;i++){
		t[++cnt]=a[i];
		t[++cnt]=LCA(a[i],a[i+1]);
	}
	sort(t+1,t+cnt+1,[&](int x,int y){return dfn[x]<dfn[y];});
	cnt=unique(t+1,t+cnt+1)-t-1;
	for(int i=1;i<=cnt;i++) G[t[i]].clear();
	for(int i=1;i<cnt;i++){
		int lca=LCA(t[i],t[i+1]);
		G[lca].push_back({t[i+1] , ask(t[i+1],lca)});   //单向边即可 
	}
}
int f[N];
void DP(int u){
	f[u]=0;
	for(PII e:G[u]){
		int v=e.fi,w=e.se;
		DP(v);
		if(flag[v]) f[u]+=w;
		else f[u]+=min(w,f[v]);
	}
}
signed main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		add(u,v,w),add(v,u,w);
	}
	dep[1]=1;
	dfs(1);
	for(int i=1;i<=20;i++){
		for(int u=1;u<=n;u++){
			fa[u][i]=fa[fa[u][i-1]][i-1];
			ming[u][i]=min(ming[u][i-1] , ming[fa[u][i-1]][i-1]);
		}
	}
	T=read();
	while(T--){
		k=read();
		for(int i=1;i<=k;i++) a[i]=read(),flag[a[i]]=true;
		Build_Virtual_Tree();
		DP(1);
		printf("%lld\n",f[1]);
		for(int i=1;i<=k;i++) flag[a[i]]=false;
	}
	return 0;
}

93.[HEOI2014] 大工程

也是裸题。

建立虚树，然后简单树形 DP 求出：\(Size_i\) 表示 \(i\) 子树内关键点数量，\(f_i\) 表示 \(i\) 到 \(i\) 子树内关键点的距离和，\(g_i\) 表示最小距离，\(h_i\) 表示最大距离。
注意到求最终答案时一条路径在有根树上肯定形如 \(x\to lca\to y\) 所以只要在 \(lca\) 处统计他即可。
所以求最终答案时只需要合并不同子树内的答案，具体的:
在用儿子 \(v\) 更新 \(u\) 的 DP 值之前， \(u\) 存的是 \(v\) 之前所有 \(v\) 的兄弟的信息，那么更新全局答案 \((sum,Min,Max)\):

\(f_u\times Size_v + w(u,v)\times Size_u\times Size_v + f_v\times Size_u \to sum\)。
\(Min= \min(Min, g_u+w(u,v)+g_v)\)。
\(Max= \max(Max, h_u+w(u,v)+h_v)\)。

\(w(u,v)\) 表示 \(u,v\) 在虚树上的边权，在原树中就是 \(dep_v-dep_u\)。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,T,tot,head[N],to[N<<1],val[N<<1],Next[N<<1];
void add(int u,int v){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
int dfn[N],dep[N],fa[N][25],num;
void dfs(int u){
	dfn[u]=++num;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i],w=val[i];
		if(v==fa[u][0]) continue;
		fa[v][0]=u;
		dep[v]=dep[u]+1;
		dfs(v);
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int t=20;t>=0;t--)
		if(dep[fa[x][t]]>=dep[y]) x=fa[x][t];
	if(x==y) return x;
	for(int t=20;t>=0;t--)
		if(fa[x][t] != fa[y][t]) x=fa[x][t],y=fa[y][t];
	return fa[x][0]; 
}
int k,a[N],t[N],cnt;
bool flag[N];
vector<int> G[N];
void Build_Virtual_Tree(){
	sort(a+1,a+k+1,[&](int x,int y){return dfn[x]<dfn[y];});
	cnt=0;
	t[++cnt]=1,t[++cnt]=a[k];
	for(int i=1;i<k;i++){
		t[++cnt]=a[i];
		t[++cnt]=LCA(a[i],a[i+1]);
	}
	sort(t+1,t+cnt+1,[&](int x,int y){return dfn[x]<dfn[y];});
	cnt=unique(t+1,t+cnt+1)-t-1;
	for(int i=1;i<=cnt;i++) G[t[i]].clear();
	for(int i=1;i<cnt;i++){
		int lca=LCA(t[i],t[i+1]);
		G[lca].push_back(t[i+1]);   
	}
}
int sum,ming,maxn,Size[N],f[N],g[N],h[N];
void DP(int u){
	Size[u]=flag[u];
	f[u]=0;
	if(flag[u]) g[u]=h[u]=0;
	else g[u]=INT_MAX,h[u]=INT_MIN;
	for(int v:G[u]){
		DP(v);
		int w=dep[v]-dep[u];
		sum += f[u]*Size[v] + w*Size[u]*Size[v] + f[v]*Size[u];
		ming = min(ming , g[u]+w+g[v]);
		maxn = max(maxn, h[u]+w+h[v]);
		Size[u]+=Size[v];
		f[u]+=f[v]+Size[v]*w;
		g[u]=min(g[u],g[v]+w);
		h[u]=max(h[u],h[v]+w);
	}
}
signed main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	dep[1]=1;
	dfs(1);
	for(int i=1;i<=20;i++){
		for(int u=1;u<=n;u++){
			fa[u][i]=fa[fa[u][i-1]][i-1];
		}
	}
	T=read();
	while(T--){
		k=read();
		for(int i=1;i<=k;i++) a[i]=read(),flag[a[i]]=true;
		Build_Virtual_Tree();
		sum=0,ming=INT_MAX,maxn=INT_MIN;
		DP(1);
		printf("%lld %lld %lld\n",sum,ming,maxn);
		for(int i=1;i<=k;i++) flag[a[i]]=false;
	}
	return 0;
}

94.[HNOI2014] 世界树

我也不太确定这个题到底该不该放进来，就当复习虚树吧。

虚树是显然的。
设 \(ans_i\) 表示关键点 \(i\) 最后的答案，称原树上离点 \(u\) 最近的关键点为 \(u\) 的对应点。
对于虚树上的点，可以换根 DP 求出 \(f_i\) 表示距离 \(i\) 号点最近的关键点的编号，我相信大家都会。
那对于不是虚树上的点怎么办?
会发现一个点不在虚树上只有两种情况:

原树上，他的这棵子树里一个关键点都没有。
他在虚树上的两个点在原树的那条链上。

对应到虚树上可以变为:

一个虚树节点 \(u\)，他在原树上有一个儿子 \(v\)，但 \(v\) 的子树中没有关键点，此时 \(v\) 子树中的所有点的对应点一定都是 \(f_u\)，所以把 \(ans_{f_u}\) 加上 \(Size_v\)。
虚树上的两个节点 \(x,y\) 其中 \(x\) 是 \(y\) 的父亲，它们在原树上可能只是祖先后代关系，它们之间的链上还有一些点。
假设其中有个点 \(c\)，当然 \(c\) 上还可能挂了一些子树，显然这些子树的 \(f\) 值和 \(c\) 的 \(f\) 值是一样。
我们可以找到这条链上的一个分割点 \(u\)，使得链上 \([u,y)\) 这段区间的对应点都是 \(f_y\)，\((x,u)\) 这段区间的对应点都是 \(f_x\)。

那具体怎么求呢？因为我们是不能去原树上遍历的。
对于 1. 中的情况：我们可以转换一下，求一个虚树点 \(u\) 所有不存在关键点的子树的大小的和，可以容斥用 \(Size_u\) 先 \(-1\) （自己），再减去所有有关键点的子树的大小。
求有关键点的子树大小只需要遍历 \(u\) 虚树上的每个儿子 \(son\)，在原树上倍增求出 \(son\) 在原树上的 \(dep_{son}-dep_u-1\) 级祖先 \(v\)，那么 \(v\) 就是 \(u\) 在原树上的儿子，再让 \(Size_u\) 减去 \(Size_v\) 即可。
最后 \(Size_u \to ans_{f_u}\)，注意 \(Size_u\) 还要还原。

对于 2. 中的情况：还是一样的对每个 \(x\)，枚举虚树上的儿子 \(y\)，然后还是倍增求出 \(x\) 在原树上含有 \(y\) 的那个儿子 \(v\)，分界点 \(u\) 是可以二分/倍增求的。
求出 \(u,v\) 之后就可以更新答案了：\(Size_v-Size_u \to ans_{f_x}\) ， \(Size_u-Size_y \to ans_{f_y}\)。
一定要注意不是用 \(Size_x-Size_u\) 去更新 \(ans_{f_x}\)。

复杂度是 \(O(\sum m \times \log n)\) 或者 \(O(\sum m \times \log^2 n)\)（如果你用二分套倍增的话）。

code

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,T,tot,head[N],to[N<<1],val[N<<1],Next[N<<1];
void add(int u,int v){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
int dfn[N],dep[N],Size[N],fa[N][25],num;
void dfs(int u){
	dfn[u]=++num;
	Size[u]=1;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i],w=val[i];
		if(v==fa[u][0]) continue;
		fa[v][0]=u;
		dep[v]=dep[u]+1;
		dfs(v);
		Size[u]+=Size[v]; 
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int t=20;t>=0;t--)
		if(dep[fa[x][t]]>=dep[y]) x=fa[x][t];
	if(x==y) return x;
	for(int t=20;t>=0;t--)
		if(fa[x][t] != fa[y][t]) x=fa[x][t],y=fa[y][t];
	return fa[x][0]; 
}
int Get(int x,int len){
	for(int t=20;t>=0;t--) if(len>>t&1) x=fa[x][t];
	return x;
} 
int dist(int x,int y){return dep[x]+dep[y]-2*dep[LCA(x,y)];}

int k,h[N],a[N],t[N],cnt;
bool flag[N];
vector<int> G[N];
void Build_Virtual_Tree(){
	sort(a+1,a+k+1,[&](int x,int y){return dfn[x]<dfn[y];});
	cnt=0;
	t[++cnt]=1,t[++cnt]=a[k];
	for(int i=1;i<k;i++){
		t[++cnt]=a[i];
		t[++cnt]=LCA(a[i],a[i+1]);
	}
	sort(t+1,t+cnt+1,[&](int x,int y){return dfn[x]<dfn[y];});
	cnt=unique(t+1,t+cnt+1)-t-1;
	for(int i=1;i<=cnt;i++) G[t[i]].clear();
	for(int i=1;i<cnt;i++){
		int lca=LCA(t[i],t[i+1]);
		G[lca].push_back(t[i+1]);   
	}
}

int f[N],ans[N];
void DP1(int u){   //先求子树中的关键点到 u 的距离最短的点 
	f[u]=(flag[u])?u:-1;
	for(int v:G[u]){
		DP1(v);
		if(f[u]==-1) f[u]=f[v];
		else if(dist(f[u],u) > dist(f[v],u)) f[u]=f[v];
		else if(dist(f[u],u) == dist(f[v],u)) f[u]=min(f[u],f[v]);
	}
}
void DP2(int u){ //换根 
	for(int v:G[u]){
		//用 u 取更新儿子,这里直接更新就可以，不需要考虑 f[u] 有没有可能在 v 子树的情况，因为这样一定不会用 f[u] 去更新 f[v] 
		if(f[v]==-1) f[v]=f[u];
		else if(dist(v,f[v]) > dist(v,f[u])) f[v]=f[u];
		else if(dist(v,f[v]) == dist(v,f[u])) f[v]=min(f[v],f[u]);
		DP2(v);
	}	
	ans[f[u]]++;
}
int check(int u,int x,int y){
	if(dist(u,x) < dist(u,y)) return x;
	else if(dist(u,x) > dist(u,y)) return y;
	else return min(x,y); 
}
void dfs1(int u){   //变量名稍有不同 
	int tmp=Size[u]-1;  //tmp 是处理第一种情况的 
	for(int v:G[u]){
		int x=Get(v,dep[v]-dep[u]-1);
		tmp-=Size[x];
		
		int l=1,r=dep[v]-dep[u]-1,mid,y=v;
		while(l<=r){
			mid=(l+r)>>1;
			if(check(Get(v,mid) , f[v] , f[u])==f[v]) l=mid+1,y=Get(v,mid);
			else r=mid-1;
		}
		ans[f[u]]+=Size[x]-Size[y];
		ans[f[v]]+=Size[y]-Size[v];
		
		dfs1(v);
	}
	ans[f[u]]+=tmp;
}
signed main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	dep[1]=1;
	dfs(1);
	for(int i=1;i<=20;i++){
		for(int u=1;u<=n;u++){
			fa[u][i]=fa[fa[u][i-1]][i-1];
		}
	}
	T=read();
	while(T--){
		k=read();
		for(int i=1;i<=k;i++) h[i]=a[i]=read(),ans[a[i]]=0,flag[a[i]]=true;
		Build_Virtual_Tree();
		DP1(1);
		DP2(1);
		dfs1(1);  //求全局答案 
		for(int i=1;i<=k;i++) printf("%d ",ans[h[i]]);  //不是 a[i],因为 a[i] 已经被排序了 
		puts("");
		for(int i=1;i<=k;i++) flag[a[i]]=false;
	}
	return 0;
}

95.[HNOI/AHOI2018] 毒瘤

来一道不是那么简单的虚树题。
我保证这是最后一道虚树题了。

题解区还有 ddp 和 广义串并联图 的做法，感兴趣的可以去看。

这个题就是求一个图的独立集个数。
对于一个树的情况，我们有 DP:

\(f_{u,0}=\prod_{v \in son(u)} f_{v,0}+f_{v,1}\)。
\(f_{u,1}=\prod_{v \in son(u)} f_{v,0}\)。

会发现非树边只有 \(m-n+1\le 11\) 条，对于这些非树边 \((u,v)\) 的两个端点状态只有三种：\((0,0),(0,1),(1,0)\)。
而且会发现假设 \(u\) 在树上是 \(v\) 的祖先（无向图搜索树没有横插边），那么我们其实只关心 \(u\) 的状态是什么，即如果 \(u\) 钦定为 \(0\)，那对 \(v\) 是没有影响的。
所以 \((0,0)\) 和 \((0,1)\) 可以合并成一个情况，合起来之后就只需要钦定 \(u\) 的状态是什么。
暴力枚举是 \(O(2^{11} n)\)。

会发现对 DP 产生影响的只有这 \(22\) 个点，考虑对他们建立虚树。
但虚树上明显不能用上面那个式子，我们来看虚树上的一条边 \((u,v)\) 在原树上对应的那条链：\(u \to x_1 \to x_2 \to … \to x_k \to v\)（\(u\) 是链顶）。
对于这条链上的一个点 \(i\)，如果定义 \(g_{i,0}=\prod f_{j,0} + f_{j,1}，g_{i,1}=\prod f_{j,0}\)，其中 \(j\) 是原树上 \(i\) 不在这条链上的儿子。
那么假设此时我们已经知道 \(v\) 的 \(f\) 值了，那么我们尝试暴力推导出这条链上其他点的 \(f\) 值:
(\(1\))

\(f_{x_k,0} = g_{x_k,0} \times (f_{v,0} + f_{v,1})\)。
\(f_{x_k,1} = g_{x_k,1} \times f_{v,0}\)。

(\(2\))

\(f_{x_{k-1},0}\)
\(= g_{x_{k-1},0} \times (f_{x_k,0} + f_{x_k,1})\)
\(= g_{x_{k-1},0} \times (g_{x_k,0} \times (f_{v,0} + f_{v,1}) + g_{x_k,1} \times f_{v,0})\)
\(= ( g_{x_{k-1},0} \times (g_{x_k,0} + g_{x_k,1}) ) \times f_{v,0} + (g_{x_{k-1},0} \times g_{x_k,0}) \times f_{v,1}\)。
\(f_{x_{k-1},1}\)
\(= g_{x_{k-1},1} \times f_{x_k,0}\)
\(= g_{x_{k-1},1} \times g_{x_k,0} \times (f_{v,0} + f_{v,1})\)
\(= g_{x_{k-1},1} \times g_{x_k,0} \times f_{v,0} + g_{x_{k-1},1} \times g_{x_k,0} \times f_{v,1}\)。

…

(\(k+1\))

\(f_{u,0} = k_{v,0,0}\times f_{v,0} + k_{v,1,0}\times f_{v,1}\)。
\(f_{u,1} = k_{v,0,1}\times f_{v,0} + k_{v,1,1}\times f_{v,1}\)。

会发现不管这个虚树上每个点的状态钦定为什么，一条边 \((u,v)\) 的系数 \(k_{v,0/1,0/1}\) 是不变的。
我们只要算出每条边的系数就可以快速进行虚树上的树形 DP。
求系数其实也不用上面写出来的那么麻烦，程序里面你就模拟展开过程即可。
容易证明暴力对于每一条链 \((u,v)\) 去计算每个链上的点的 \(g\) 值和系数的总复杂度是 \(O(n)\) 的。

但此时会有个问题，就是 \(u\) 可能在虚树上不止一个儿子，即他可能还有一个虚树上的儿子 \(w\)，那在处理 \((u,v)\) 算 \(g_u\) 时，会需要用到 \(w\) 那棵子树的 DP 值，这样当去处理 \((u,w)\) 时就算重了。
处理方法也比较简单，把 \(g\) 的定义改一下:
\(g_{i,0}=\prod f_{j,0} + f_{j,1}，g_{i,1}=\prod f_{j,0}\)，其中 \(j\) 是 \(i\) 在原树上的儿子，且 \(j\) 这棵子树里不存在虚树上的点。
容易发现那些 \(x_1,x_2,…,x_k\) 的 \(g\) 值还是不变的。
但注意的是此时在算 \(k_{v,0/1,0/1}\) 时就不要再把 \(u\) 的 \(g\) 值算进去了，即此时 \(k_{v,0,0}\times f_{v,0} + k_{v,1,0}\times f_{v,1}\) 算出来的并不是 \(f_{u,0}\) 而是 \(f_{x_k,0}\)。

那么在虚树上 DP 时，\(f_{u,0}\) 的值就是:

\[\begin{aligned} f_{u,0} &= g_{u,0} \times \prod(f_{x,k,0} + f_{x_k,1}) \\ &= g_{u,0} \times \prod(k_{v,0,0}\times f_{v,0} + k_{v,1,0}\times f_{v,1} +k_{v,0,1}\times f_{v,0} + k_{v,1,1}\times f_{v,1}) \\ \end{aligned} \]

复杂度是：\(O(2^K K)\)，\(K=m-n+1\)。

code

#include<bits/stdc++.h>
#define PII pair<int,int>
#define int long long 
#define fi first
#define se second
using namespace std;
const int N=1e5+15,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,tot,head[N],to[N<<1],Next[N<<1];
void add(int u,int v){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}

int dfn[N],dep[N],fa[N][25],num,cnt;
PII e[N];  //存非树边 
void dfs1(int u){    
	dfn[u]=++num;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa[u][0]) continue;
		if(!dfn[v]){
			fa[v][0]=u,dep[v]=dep[u]+1;
			dfs1(v);
		} 
		else if(dfn[v]<dfn[u]) e[++cnt]={v,u};
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int t=20;t>=0;t--)
		if(dep[fa[x][t]]>=dep[y]) x=fa[x][t];
	if(x==y) return x;
	for(int t=20;t>=0;t--)
		if(fa[x][t] != fa[y][t]) x=fa[x][t],y=fa[y][t];
	return fa[x][0]; 
}

int k,h[N],a[N],t[N],c;
bool flag[N];
vector<int> G[N];
void Build_Virtual_Tree(){
	sort(a+1,a+k+1,[&](int x,int y){return dfn[x]<dfn[y];});
	k=unique(a+1,a+k+1)-a-1;
	c=0;
	t[++c]=1;
	if(k) t[++c]=a[k];
	for(int i=1;i<k;i++){
		t[++c]=a[i];
		t[++c]=LCA(a[i],a[i+1]);
	}
	sort(t+1,t+c+1,[&](int x,int y){return dfn[x]<dfn[y];});
	c=unique(t+1,t+c+1)-t-1;
	for(int i=1;i<=c;i++) flag[t[i]]=true,G[t[i]].clear();

	for(int i=1;i<c;i++){
		int lca=LCA(t[i],t[i+1]);
		G[lca].push_back(t[i+1]);   
	}
}

void Init(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		add(u,v),add(v,u); 
	} 
	dep[1]=1;
	dfs1(1);
	for(int i=1;i<=20;i++)
		for(int u=1;u<=n;u++)
			fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=1;i<=cnt;i++) a[++k]=e[i].fi,a[++k]=e[i].se;
	
	Build_Virtual_Tree(); 
}



int f[N][2],g[N][2];
bool stater[N];  //子树里是否有虚树上的点 
void dfs2(int u){    //预处理 g 数组 
	stater[u]=flag[u];
	f[u][0]=f[u][1]=g[u][0]=g[u][1]=1;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa[u][0] || fa[v][0]!=u) continue; 
		dfs2(v);
		stater[u]|=stater[v];
		( f[u][0] *= (f[v][0] + f[v][1]) % mod) %= mod;
		( f[u][1] *= f[v][0] ) %= mod;
		if(!stater[v]){
			( g[u][0] *= (f[v][0] + f[v][1]) % mod) %= mod;
			( g[u][1] *= f[v][0] ) %= mod;
		} 
	}
}

int K[N][2][2],tmp[2][2];  //系数，因为上面小写 k 用过了，所以大写 
void solve(int u,int v){   //预处理 K[v][0/1][0/1] 
	K[v][0][0]=K[v][1][1]=1;
	int x=fa[v][0];
	while(x!=u){
		tmp[0][0]=K[v][0][0],tmp[0][1]=K[v][0][1],tmp[1][0]=K[v][1][0],tmp[1][1]=K[v][1][1];
		K[v][0][0] = ( tmp[0][0] + tmp[0][1] ) % mod * g[x][0] % mod;
		K[v][1][0] = ( tmp[1][0] + tmp[1][1] ) % mod * g[x][0] % mod;
		K[v][0][1] = tmp[0][0] * g[x][1] % mod;
		K[v][1][1] = tmp[1][0] * g[x][1] % mod; 
		x=fa[x][0];
	}
}

void Get_DP(){
	dfs2(1);
	for(int u=1;u<=n;u++)
		for(int v:G[u]) solve(u,v);
}



void DP(int u){
	(f[u][0]*=g[u][0])%=mod,(f[u][1]*=g[u][1])%=mod;
	for(int v:G[u]){
		DP(v);
		( f[u][0] *= ( (K[v][0][0] * f[v][0] % mod + K[v][1][0] * f[v][1] % mod) % mod + ( K[v][0][1] * f[v][0] % mod + K[v][1][1] * f[v][1] % mod) % mod ) % mod ) %= mod;
		( f[u][1] *= (K[v][0][0] * f[v][0] % mod + K[v][1][0] * f[v][1] % mod) % mod ) %= mod;
	}
}
void work(){
	int ans=0;
	for(int S=0;S<(1<<cnt);S++){
		for(int i=1;i<=c;i++) f[t[i]][0]=f[t[i]][1]=1;
		for(int i=1;i<=cnt;i++)
			if(S>>(i-1)&1) f[e[i].fi][0]=0,f[e[i].se][1]=0;
			else f[e[i].fi][1]=0;
		DP(1);
		( ans += (f[1][0] + f[1][1]) % mod ) %= mod;
	}
	printf("%lld\n",ans);
}
signed main(){
	Init();
	Get_DP(); 
	work();
	return 0;
}

96.[HNOI2004] L 语言

先看朴素的 DP，设 \(f_i\) 表示前缀 \(i\) 可不可以被理解，转移是：\(f_j \to f_i\)，需要满足 \(s[j+1,i]\) 是一个单词。

考虑对字典里的模式串建出 AC 自动机。
如果 \(t\) 的前缀 \(i\) 在 fail 树上代表点 \(u\)，并且他的一个祖先 \(v\) 是一个模式串的终止节点。
设 \(v\) 代表的模式串长度为 \(len\)，则 \(i\) 的长度为 \(len\) 的后缀就是一个模式串。
也就意味着 \(f_{i-len}\) 可以转移到 \(f_i\)。
如果在 fail 树上暴力地跳，并挨个判断每个祖先，那么是 \(O(m|s||t|)\) 的。

注意到 \(|s|\le 20\)，也就是说所有以 \(u\) 结尾的模式串的长度是可以状压的，我们记在 \(g\) 数组里面，即 \(g_u\) 的第 \(k\) 位是 \(1\) 代表 \(u\) 结尾有一个长度为 \(k\) 的模式串。
又因为能转移到 \(f_i\) 的 \(f_j\) 必定满足 \(j\ge i-|s|\)，所以我们也可以对 \(f\) 数组状压，记在 \(h\) 数组里，即如果 \(h_i\) 的第 \(k\) 位是 \(1\) 那么代表 \(f_{i-k}=true\)。
所以 \(f_i = [(g_u | h_i) \ne 0]\)，\(u\) 是前缀 \(i\) 在 fail 树上代表的点。
其中 \(g\) 可以预处理，\(h\) 数组在转移的时候维护就可以了。

复杂度是：\(O(\sum |s| + \sum |t|)\)。

code

#include<bits/stdc++.h>
using namespace std;
const int N=500+5,M=2e6+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
string s;
int n,T,tot,t[N][30],len[N],flag[N];
void insert(string s){  
	int p=0,dep=0;
	for(int i=0;i<s.size();i++){
		int ch=s[i]-'a';
		if(!t[p][ch]) t[p][ch]=++tot;
		p=t[p][ch],++dep;
	}
	flag[p]=1;
	len[p]=dep;
}

int fail[N];
vector<int> G[N];
void getfail(){
	queue<int> q;
	for(int i=0;i<26;i++){
		if(t[0][i]) q.push(t[0][i]);
	}
	while(q.size()){
		int u=q.front(); q.pop();
		for(int i=0;i<26;i++){
			if(t[u][i])
				fail[t[u][i]]=t[fail[u]][i],q.push(t[u][i]);
			else
				t[u][i]=t[fail[u]][i];
		}
	}
	for(int i=1;i<=tot;i++) G[fail[i]].push_back(i);
}

int g[M];
bool f[M];
void dfs(int u){
	for(int v:G[u]){
		g[v]=g[u] | (flag[v] * (1<<len[v])); 
		dfs(v);
	} 
}

void Init(){
	memset(f,false,sizeof f);
} 
signed main(){
	ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	cin>>n>>T;
	for(int i=1;i<=n;i++){
		cin>>s;
		insert(s);
	}
	getfail();
	dfs(0);
	while(T--){
		Init();
		cin>>s; s=' '+s;
		int p=0,h=1,ans=0;
		for(int i=1;i<s.size();i++){
			p=t[p][s[i]-'a'];
			h<<=1;
			if((h&g[p])!=0) f[i]=true,ans=max(ans,i);
			h|=f[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}

来源链接：https://www.cnblogs.com/FloatingLife/p/18808309

评分

欢迎为Ta评分