jzoj 1752. 无聊的草稿 树形DP | 两遍dfs

mac2022-09-22  6

Description   图中有N个点,每两点间只有唯一的路径,对于这样一个给定的图,最大的“毛毛虫”会有多大。毛毛虫包含一条主链,毛毛虫中的节点,要不在主链上,要么和主链上某节点相邻,如下图所示有两只合法的毛毛虫,点数越多,毛毛虫越大。    Input   输入文件第一行两个整数N,M(N≤1000000)   接下来M行,每行两个整数a, b(a, b≤N)   你可以假定没有一对相同的(a, b)会出现一次以上。

Output   一个整数ans,表示最大的毛毛虫的大小。

Sample Input 5 4 1 2 1 3 4 1 5 1

Sample Output 5

Data Constraint

Hint 【数据规模】   1. 对于20%的数据,N≤200   2. 对于40%的数据,N≤5000   3. 对于100%的数据,N≤10^6

对于这道题,我们可用两种方法来解决这道题

solution1:两遍dfs求树上最长链

我们先记录下每个点所连接的边数,每次dfs记录下当前答案和ans比较,如果比ans大,那么我们就记录当前值一遍dfs之后,我们用得出的那个值作为端点再次进行dfs,然后就可以得出答案考虑细节,第一次dfs之后,记得把数组清空,从端点开始dfs时,答案从1开始累加,之后每次加上它的边数时要减去1,因为这个1已经从父亲转移时已经加上

AC代码

#include<cstdio> #include<cstring> #define si 1000010 #define re register int using namespace std; struct edge { int nex,to; }e[si<<1]; int n,m,ans,cnt,pos,a[si],head[si]; bool v[si]; inline int read() { int x=0,cf=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') cf=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return x*cf; } inline void add(int x,int y) { e[++cnt].to=y,e[cnt].nex=head[x],head[x]=cnt; } inline void dfs(int x,int t,int op) { v[x]=true; for(re i=head[x];i;i=e[i].nex) { int y=e[i].to; if(v[y]) continue; if(op) dfs(y,t+a[y],0); else dfs(y,t+a[y]-1,0); } if(t>ans) ans=t,pos=x; } int main() { n=read(),m=read(); for(re i=1;i<=m;i++) { int x=read(); a[x]++; int y=read(); a[y]++; add(x,y),add(y,x); } dfs(1,1,1); memset(v,0,sizeof(v)); dfs(pos,1,1); printf("%d",ans); return 0; }

solution2:树形DP

对于这道题,考虑本质,其实就是给你一棵树,求树上最长链及其最长链上连接的点定义状态:设数组f[x]记录从x开始不含x以及x的父亲的最大毛毛虫对于每一个节点x,我们用数组s来记录x所有连接的点数(不包含x的父节点)考虑状态转移,对于每一个节点,每次都从他的子节点加上自己的所有连接点数注意细节:数组记得要开大,每次取ans时,我们要判断当前是否是根节点,如果是根节点,那么我们就不能加1,否则需要再加1

AC代码

#include<bits/stdc++.h> #define size 1000010 using namespace std; struct edge { int next,to; }e[size<<1]; int n,m,cnt,ans,val,head[size],f[size],s[size]; void add(int x, int y) { e[++cnt].to=y,e[cnt].next=head[x],head[x]=cnt; } void dfs(int x,int fa) { for(int i=head[x];i;i=e[i].next) { int y=e[i].to; if(y==fa) continue; s[x]++; } for(int i=head[x];i;i=e[i].next) { int y=e[i].to; if(y==fa) continue; dfs(y,x); if(fa>0) val=1; else val=0; ans=max(ans,f[x]+f[y]+1+val); f[x]=max(f[x],f[y]+s[x]); } } int main() { cin>>n>>m; for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y),add(y,x); } dfs(1,0); cout<<ans; return 0; }

如果有洛谷号,还可以做一下这道题 多道紫题

最新回复(0)