zhxfl hdu 3534 树形dp,求最长路径有多少条,存在负权边

《zhxfl hdu 3534 树形dp,求最长路径有多少条,存在负权边》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#include#include#includeusingnamespacestd;#definemaxn10001#defineinf0x7ffffffintdis[maxn];structCoor{   intx,v;};vectorv[maxn];structNode{   intMax1,Max2,Max,num1,num2,num;}node[maxn];//node[x]中记录的是：//x的子节点通过x的最长路径为Max，条数为num，//Max1是x的子节点到x的最长距离，num

2、1是条数//Max2是x的子节点到x的次长距离，num2是条数voiddfs(intx,intf){   inti;   for(i=0;i

3、//如果是叶子，num1记录为1   boolflag=1;   //找出距离最长的叶子   for(i=0;inode[x].Max1)       {           flag=0;           node[x].Max1=dis[u]+w;           node[x].num1=node[u].num1;           node[x].num=0;  

4、     }       elseif(dis[u]+w==node[x].Max1)       {           node[x].num+=node[x].num1*node[u].num1;//最长的叶子超过1个，可以算出经过x的最长路径有多少个           node[x].num1+=node[u].num1;       }   }   if(node[x].num==0)//如果最长路径的个数还没有统计出来,统计第二长的   {       for(i=0;i

5、       intw=v[x][i].v;           if(u==f)continue;           if(dis[u]+w==node[x].Max1)continue;           if(dis[u]+w>node[x].Max2)           {               node[x].Max2=dis[u]+w;               node[x].num2=node[u].num1;           }           elseif(dis[u]+w==node[x].Max2)           {             

6、  node[x].num2+=node[u].num1;           }       }       if(node[x].num2)//第二长的不是0       {           node[x].num=node[x].num1*node[x].num2;           node[x].Max=node[x].Max1+node[x].Max2;       }       else//第二长的为0       {           node[x].Max=node[x].Max1;           node[x].num=node[x].num1;      

7、 }   }   else   {       node[x].Max=node[x].Max1*2;   }   if(flag)node[x].num1=1;   dis[x]=node[x].Max1;}intmain(){   inti,j,n,x,y;   Coorcoor;   //freopen("a.txt","r",stdin);   while(scanf("%d",&n)!=