树形DP还有一种特殊情况——基环树的DP，基环树就是一颗树上再加一条边，处理基环树问题时一般先找出环再处理，然后再搞来搞去就行啦

BZOJ1040 找到环上任意一边对两种情况分类讨论就可以在树上DP啦

#include<cstdio>
#include<algorithm>
#define N 1111111
using namespace std;
int n,i,x,tot,R,R1,R2,ban,last[N<<1],next[N<<1],first[N];
long long tmp,ans,dp[N][2],a[N];
bool v[N];
void ins(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
void dfs(int x,int fa){
	v[x]=1;
	for(int i=first[x];i;i=next[i]){
		int y=last[i];
		if(y==fa)continue;
		if(v[y])R1=x,R2=y,ban=i;else dfs(y,x);
	}
}
void solve(int x,int fa){
	dp[x][0]=0;dp[x][1]=a[x];
	for(int i=first[x];i;i=next[i])if(i!=ban&&(i!=(ban^1))){
		int y=last[i];
		if(y!=fa){
			solve(y,x);
			dp[x][0]+=max(dp[y][0],dp[y][1]);
			dp[x][1]+=dp[y][0];
		}
	}
	if(x==R)dp[x][1]=-1e16;
}
int main(){
	scanf("%d",&n);tot=1;
	for(i=1;i<=n;i++){
		scanf("%lld%d",&a[i],&x);
		ins(i,x);ins(x,i);
	}
	for(i=1;i<=n;i++)if(!v[i]){
		dfs(i,0);
		R=R1;solve(i,0);tmp=max(dp[i][0],dp[i][1]);
		R=R2;solve(i,0);ans+=max(tmp,max(dp[i][0],dp[i][1]));
	}
	printf("%lld",ans);
}

BZOJ1791 找基环树上的最大直径：先找出环，很明显答案有两种情况，一种是在以一个环上节点为根的外向树的直径，一种是以两个环上节点分别为根的最大深度再加上两个节点在环上距离。第一种情况非常好处理，对每个节点两遍DFS就可以啦，第二种情况要处理出以环上每个节点为根的最大深度d[i]，以环上一个节点作为基准点求前缀和sum[i]，设我们找的两个环上节点是i,j

则max(max(s[i]-s[j],sum-(s[i]-s[j])+d[i]+d[j])即为所求，但如果暴力求是n^2的，要超时

我们可以把式子变形一下变为max(s[i]+d[i]-s[j]+d[j],sum-s[i]+d[i]+s[j]+d[j])，然后发现s[i]+d[i]和sum-s[i]+d[i]都是常数

只需要维护-s[j]+d[j]和s[j]+d[j]的最大值就可以做到O(n)啦。。

找环的时候由于题目的特殊性质可以用简单的方法找，代码长度就碾压啦！

不过如果是一般图，我就不知道怎么找啦、、到时候学一下。。

#include<cstdio>
#include<algorithm>
#define N 1111111
#define inf 1e15
using namespace std;
int n,i,j,x,u,sz,num,tot,to[N],cir[N],fa[N],v[N],fir[N],ne[N<<1],la[N<<1];
long long l,now,ans,mav,mav2,zs,n1,n2,va[N<<1],sum[N],d[N],len[N];bool c[N],vis[N],vis2[N];
void ins(int x,int y,long long z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void fcur(int x){//找环 
	v[x]=++sz;int y;
	for(;true;x=y){
		y=to[x];
		if(v[y]){
			cir[++num]=y;c[y]=1;
			for(;x!=y;x=fa[x])c[x]=1,cir[++num]=x,sum[num]=sum[num-1]+len[x];
			zs=sum[num]+len[cir[1]];return;
		}
		fa[y]=x;v[y]=1;
	}
}
void ghigh(int x,long long high){//第一遍DFS 
	vis[x]=1;if(high>mav)mav=high,u=x;
	for(int i=fir[x];i;i=ne[i])if(!vis[la[i]]&&!c[la[i]])ghigh(la[i],high+va[i]);
}
void ghigh2(int x,long long high){//第二遍DFS 
	vis2[x]=1;if(high>mav2)mav2=high;
	for(int i=fir[x];i;i=ne[i])if(!vis2[la[i]]&&!c[la[i]])ghigh2(la[i],high+va[i]);
}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d%lld",&x,&l),to[i]=x,len[i]=l,ins(i,x,l),ins(x,i,l);
	for(i=1;i<=n;i++)if(!v[i]&&!vis2[i]&&!vis[i]){
		num=0;now=-inf;fcur(i);
		for(j=1;j<=num;j++){//对环上每个节点为根做DFS得到d[j]和该树直径更新答案 
			mav=-inf;mav2=-inf;ghigh(cir[j],0);
			c[cir[j]]=0;ghigh2(u,0);c[cir[j]]=1;
			d[j]=mav;now=max(now,mav2);
		}
		n1=inf;n2=-inf;//n1为min(sum[j]-d[j]),n2为max(sum[j]+d[j])，用这两个值快速更新答案 
		for(j=1;j<=num;j++){//更新答案 
			now=max(now,max(sum[j]+d[j]-n1,zs-(sum[j]-d[j])+n2));
			n1=min(n1,sum[j]-d[j]);n2=max(n2,sum[j]+d[j]);
		}
		ans+=now;
	}
	printf("%lld",ans);
}

然后弄了好久总算发现一种不错的找环方法。。

v[x]=++sz;
for(int i=fir[x];i;i=ne[i]){
    int y=la[i];
    if(y==fa[x])continue;
    if(v[y]){
        if(v[y]<v[x])continue;
        cir[++num]=x;c[x]=1;
        for(;x!=y;y=fa[y])c[y]=1,cir[++num]=y;
    }else fa[y]=x,fcur(y);
}

BZOJ2878迷失游乐园 基环树上求期望

考虑用down[x]表示向下走的期望步数，up[x]表示向上走的期望步树。

对于每颗外向树，第一遍DFS求出down[x]=(Σdown[y]+v[<x,y>])/son[x]（son[x]表示x儿子数）

第二遍DFS求出up[y]=(up[x]*sg[x]+son[x]*down[x]-down[y]-v[<x,y>])/(sg[x]+son[x]+1)（sg[x]表示x父亲数）

但由于有环，在环上我们要进行特殊处理

可以对环上每个节点逆时针、顺时针各弄一圈算出up[]的答案，再进行第二回DFS就行啦，这时环上每个节点的sg[]为2

#include<cstdio>
#define N 100010
int n,m,i,j,x,y,tot,sz,num,cir[N],pre[N],v[N],fa[N],la[N<<1],ne[N<<1],fir[N];
double z,ans,son[N],up[N],down[N],va[N<<1],sg[N];bool c[N];
void ins(int x,int y,double z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void fcur(int x){
	v[x]=++sz;
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(y==pre[x])continue;
		if(v[y]){
			if(v[y]<v[x])continue;
			cir[++num]=x;c[x]=1;sg[x]=2;
			for(;x!=y;y=pre[y])c[y]=1,sg[y]=2,cir[++num]=y;
		}else pre[y]=x,fcur(y);
	}
}
double dcir(int x,int pr,int en){
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(c[y]&&y!=pr){
			if(y!=en)return (down[x]*son[x]+va[i]+dcir(y,x,en))/(son[x]+1);else return down[x];
		}
	}
}
void dfs1(int x){
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(!c[y]&&fa[x]!=y){
			fa[y]=x;son[x]++;sg[y]++;
			dfs1(y);
			down[x]+=down[y]+va[i];
		}
	}
	if(son[x])down[x]/=son[x];
}
void dfs2(int x,int f,double e){
	up[x]=e;
	if(sg[f]+son[f]>1)up[x]+=(sg[f]*up[f]+son[f]*down[f]-down[x]-e)/(sg[f]+son[f]-1);
	for(int i=fir[x];i;i=ne[i])if(la[i]!=f)dfs2(la[i],x,va[i]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d%d%lf",&x,&y,&z),ins(x,y,z),ins(y,x,z);
	if(m<n){
		dfs1(1);
		for(int i=fir[1];i;i=ne[i])dfs2(la[i],1,va[i]);
	}else{
		fcur(1);
		for(i=1;i<=num;i++)dfs1(cir[i]);
		for(j=1;j<=num;j++){
			x=cir[j];
			for(i=fir[x];i;i=ne[i]){
				if(!c[y=la[i]])continue;
				up[x]+=dcir(y,x,x)+va[i];
			}
			up[x]/=2;
		}
		for(i=1;i<=num;i++)for(j=fir[cir[i]];j;j=ne[j])if(!c[la[j]])dfs2(la[j],cir[i],va[j]);
	}
	for(i=1;i<=n;i++)ans+=(down[i]*son[i]+up[i]*sg[i])/(son[i]+sg[i]);
	printf("%.5lf",ans/n);
}

BZOJ3242 维护f[i]+s[i]和f[i]-s[i]的最值，分类讨论单调转移就可以了

#include<bits/stdc++.h>
#define N 100002
using namespace std;bool c[N];long long f[N],g[N],h[N],G[N],H[N],S,V,A,B;int n,i,x,y,z,id,t,tot,v[N],F[N],d[N],C[N],fir[N],ne[N*2],la[N*2],va[N*2],L[N];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void fcur(int x){
	v[x]=++id;
	for(int i=fir[x],y,j;i;i=ne[i]){
		y=la[i];if(F[x]==y)continue;
		if(!v[y])F[y]=x,L[y]=va[i],fcur(y);else if(v[y]>v[x]){
			for(c[x]=1;x!=y;y=F[y])C[++t]=y,d[t]=L[y],c[y]=1;
			C[++t]=x,d[t]=va[i];
		}
	}
}
void dfs(int x,int fa){for(int i=fir[x],y;i;i=ne[i])if(!c[y=la[i]]&&y!=fa)dfs(y,x),A=max(A,f[x]+f[y]+va[i]),f[x]=max(f[x],f[y]+va[i]);}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
	for(fcur(1),i=1;i<=t;i++)dfs(C[i],0);
	for(i=1;i<=t;i++)S+=d[i-1],g[i]=max(g[i-1],f[C[i]]+S),h[i]=max(h[i-1],f[C[i]]+S+V),V=max(V,f[C[i]]-S);
	for(d[0]=d[t],S=V=d[t]=0,i=t;i;i--)S+=d[i],G[i]=max(G[i+1],f[C[i]]+S),H[i]=max(H[i+1],f[C[i]]+S+V),V=max(V,f[C[i]]-S);
	for(B=h[t],i=1;i<t;i++)B=min(B,max(g[i]+G[i+1]+d[0],max(h[i],H[i+1])));
	printf("%.1lf",(double)max(A,B)/2);
}

BZOJ2791 基环树上求LCA 如果在一棵外向树上直接求，否则算环上距离判断后再求出

#include<cstdio>
#include<algorithm>
#define N 500500
using namespace std;
int n,Q,i,j,top,tm,tmp,x,y,t,x1,y1,x2,y2,to[N],pos[N],rt[N],v[N],bl[N],sz[N],h[N],fa[N][20];
void fcur(int x){
	v[x]=tm;int y;
	if(v[to[x]]==tm){
		for(y=x,tmp=0;!tmp||x!=y;y=to[y],tmp++)bl[y]=tm,pos[y]=tmp,rt[y]=y;
		sz[tm]=tmp;return;
	}
	if(!v[to[x]])fcur(to[x]);
	if(!bl[x])fa[x][0]=to[x],h[x]=h[to[x]]+1,rt[x]=rt[to[x]];
}
int lca(int x,int y){
	if(h[x]<h[y])swap(x,y);
	int t=h[x]-h[y],i;
	for(i=0;i<=19;i++)if(t&(1<<i))x=fa[x][i];
	for(i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return x==y?x:fa[x][0];
}
int dis(int x,int y,int p){return (y-x+p)%p;}
int main(){
	for(scanf("%d%d",&n,&Q),i=1;i<=n;i++)scanf("%d",&to[i]);
	for(i=1;i<=n;i++)if(!v[i])tm++,fcur(i);
	for(j=1;j<=19;j++)for(i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];
	for(;Q--;){
		scanf("%d%d",&x,&y);
		if(bl[rt[x]]!=bl[rt[y]]){puts("-1 -1");continue;}
		if(rt[x]==rt[y]){
			t=lca(x,y);
			printf("%d %d\n",h[x]-h[t],h[y]-h[t]);
			continue;
		}
		x1=h[x]+dis(pos[rt[x]],pos[rt[y]],sz[bl[rt[x]]]);y1=h[y];
		x2=h[x];y2=h[y]+dis(pos[rt[y]],pos[rt[x]],sz[bl[rt[y]]]);
		if(max(x1,y1)<max(x2,y2))printf("%d %d\n",x1,y1);else
		if(max(x2,y2)<max(x1,y2))printf("%d %d\n",x2,y2);else
		if(min(x1,y1)<min(x2,y2))printf("%d %d\n",x1,y1);else
		if(min(x2,y2)<min(x1,y1))printf("%d %d\n",x2,y2);else
		printf("%d %d\n",max(x1,y1),min(x1,y1));
	}
}

• 相关文章推荐
• 全局相关文章