首页 > 代码库 > [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 }
View Code

 

[haoi2009]毛毛虫 树形dp