/* * this is slow by #node times * * because * this program do not decide root. * every nodes are equal. * */ #include #include #define SIZE 10000 // 4 MapTables int NxN_E[SIZE][SIZE]; int N_N[SIZE][SIZE]; int N_E[SIZE][SIZE]; int E_ExE[SIZE*5000][4]; int number_of_leaf_edge; int a[SIZE], b[SIZE], tax[SIZE]; int e=0,count=0,taxsum = 0; int COMPLETE = 0; int stay[SIZE]; void expand_edge(); int find_edge(); void paytax(); void move_and_paytax(); int write_E_ExE(n1,n2,e1,e2){ E_ExE[++e][0]=n1; E_ExE[e][1]=n2; E_ExE[e][2]=e1; E_ExE[e][3]=e2; return e; } void write_N_E(n1,n2,edge){ N_E[n1][++N_E[n1][0]]=edge; N_E[n2][++N_E[n2][0]]=edge; } void write_NxN_E(u,v,edge){ NxN_E[u][v]=edge; NxN_E[v][u]=edge; } void write_N_N(n1,n2){ N_N[n1][++N_N[n1][0]]=n2; N_N[n2][++N_N[n2][0]]=n1; } int write_maps(n1,n2,e1,e2){ if (NxN_E[n1][n2]) { return NxN_E[n1][n2]; } if (n1 == n2) { return -1; } int edge = write_E_ExE(n1,n2,e1,e2); write_N_E(n1,n2,edge); write_NxN_E(n1,n2,edge); return edge; } int otherNode(edge,node){ if (node==E_ExE[edge][0]) return E_ExE[edge][1]; else return E_ExE[edge][0]; } int isLeaf(node){ if (N_N[node][0]==1) return 1; else if (N_N[node][0]>1) return 0; else {printf("N_N map error : node %d is invalid",node);return (-1);} } void push(int u, int v){ int l,L,m,R,r, P,E, length_u,length_v,length_v2, i,j; // write parent( leaf edge ) P = write_maps(u,v,0,0); write_N_N(u,v); length_u = N_E[u][0]; length_v = N_E[v][0]; // write composition of edge m = u; R = P; r = v; // now N_E[u][length_u] is P for (i=1; i0;i++){ paytax(stay[i]); } } void expand_edge(leftNode,edge){ int e0,e1,e2,e3, leaf=0,l,L,m,R,r; e0=E_ExE[edge][0];e1=E_ExE[edge][1]; e2=E_ExE[edge][2];e3=E_ExE[edge][3]; if (e2==0 && e3==0) leaf=1; if (leaf) { stay[count++]=leftNode; return; } l = leftNode; r = otherNode(edge,l); if ( l == E_ExE[e2][0] || l == E_ExE[e2][1] ) L = e2; else if ( l == E_ExE[e3][0] || l == E_ExE[e3][1] ) L = e3; else printf("expand_error : cannot find Left Edge\n"); m = otherNode(L,l); R = NxN_E[m][r]; expand_edge(l,L); expand_edge(m,R); }