首页 > 代码库 > [haoi2009]毛毛虫 树形dp
[haoi2009]毛毛虫 树形dp
这道题细节处理不少，但要AC不难；
设以i节点为根节点的子树能形成的最大的毛毛虫长度为f[i]，则f[i]=max(f[j])+i节点的孩子数；
答案需要f最大和次大的两个子树合并，而且若合并的位置不是根节点，ans++；
我就是坑在了最后一点上，最后打表找到了问题；
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int maxn=303000; 6 int n,m,f[maxn],child[maxn]; 7 struct node{ 8 int y,next; 9 }e[maxn<<1];10 int linkk[maxn],len=0;11 void insert(int x,int y){12 e[++len].y=y;13 e[len].next=linkk[x];14 linkk[x]=len;15 }16 void init(){17 scanf("%d%d",&n,&m);18 int x,y;19 for(int i=1;i<=m;i++){20 scanf("%d%d",&x,&y);21 insert(x,y);insert(y,x);22 }23 }24 void dfs(int x,int fa){25 for(int i=linkk[x];i;i=e[i].next){26 if(e[i].y==fa)continue;27 child[x]++;28 dfs(e[i].y,x);29 }30 }31 int ans=0;32 void Dfs(int x,int fa){33 if(child[x]==0){34 f[x]=1;return;35 }36 int maxx[2]={0,0};37 for(int i=linkk[x];i;i=e[i].next){38 if(e[i].y==fa)continue;39 Dfs(e[i].y,x);40 f[x]=max(f[x],f[e[i].y]+child[x]);41 if(f[e[i].y]>maxx[0])maxx[0]=f[e[i].y];42 if(f[e[i].y]>maxx[1])maxx[0]=maxx[1],maxx[1]=f[e[i].y];43 }44 ans=max(ans,f[x]+maxx[0]-1);45 if(x!=1)ans=max(ans,f[x]+maxx[0]);46 if(maxx[0]==0)ans=max(ans,f[x]);47 }48 void work(){49 dfs(1,0);50 Dfs(1,0);51 printf("%d\n",ans);52 }53 int main(){54 freopen("1.in","r",stdin);55 freopen("1.out","w",stdout);56 init();57 work();58 }
[haoi2009]毛毛虫 树形dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。