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

#include#include#include#includeusing namespace std;#define maxn 10001#define inf 0x7ffffffint dismaxn;struct Coor int x,v;vectorvmaxn;struct Node int Max1,Max2,Max,num1,num2,num; nodemaxn;/nodex中记录的是：/x的子节点通过x的最长路径为Max，条数为num，/Max1是x的子节点到x的最长距离，num1是条数/Max2是x的子节点到x的次长距离，num2是条数void dfs(int x,int f) int i; for(i=0; ivx.size(); i+) int u=vxi.x; if(u=f)continue; dfs(u,x); disx=nodex.Max1=nodex.Max2=nodex.Max=nodex.num=nodex.num1=nodex.num2=0; if(vx.size()=1&x!=1)nodex.num1=nodex.num2=1;/如果是叶子，num1记录为1 bool flag=1; /找出距离最长的叶子 for(i=0; inodex.Max1) flag=0; nodex.Max1=disu+w; nodex.num1=nodeu.num1; nodex.num=0; else if(disu+w=nodex.Max1) nodex.num+=nodex.num1*nodeu.num1;/最长的叶子超过1个，可以算出经过x的最长路径有多少个 nodex.num1+=nodeu.num1; if(nodex.num=0)/如果最长路径的个数还没有统计出来,统计第二长的 for(i=0; inodex.Max2) nodex.Max2=disu+w; nodex.num2=nodeu.num1; else if(disu+w=nodex.Max2) nodex.num2+=nodeu.num1; if(nodex.num2)/第二长的不是0 nodex.num=nodex.num1*nodex.num2; nodex.Max=nodex.Max1+nodex.Max2; else/第二长的为0 nodex.Max=nodex.Max1; nodex.num=nodex.num1; else nodex.Max=nodex.Max1*2; if(flag)nodex.num1=1; disx=nodex.Max1;int main() int i,j,n,x,y; Coor coor; /freopen(a.txt,r,stdin); while(scanf(%d,&n)!=EOF) for(i=1; i=n; i+) vi.clear(); disi=0; for(i=1; in; i+) scanf(%d%d%d,&x,&y,&coor.v); coor.x=x; vy.push_back(coor); coor.x=y; vx.push_back(coor); dfs(1,-1); int M=0; int N=0; for(i=1; iM) M=nodei.Max; N=nod