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

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; }

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