#include #include #define SIZE 100000 int number_of_nodes; int number_of_merchants; int path[SIZE][1000]; int path2[SIZE][1000]; int N_N[SIZE][1000]; int tax[SIZE]; int c,rootfound,root,taxsum; void push_N_N(); int select_root(); void order_nodes(); void expand_to_root(); void remove_verbose_path(); void paytax(); void push_N_N(u,v){ N_N[u][++N_N[u][0]]=v; N_N[v][++N_N[v][0]]=u; } int select_root(){ int i,r,max=0; for (i=1;i<=number_of_nodes;i++) if (N_N[i][0]>max){ max = N_N[i][0]; r = i; } return r; } void order_nodes(root,parent){ int i; for (i=1;i<=N_N[root][0];i++) { if (N_N[root][i] == parent) N_N[root][i]*=(-1); else order_nodes(N_N[root][i],root); } } void expand_to_root(u,mer){ path[mer][++path[mer][0]]=u; if (u==root) return; int i,ret; for (i=1;i<=N_N[u][0];i++){ ret = -(N_N[u][i]); if (ret > 0) expand_to_root(ret,mer); } } void expand_to_root2(u,mer){ path2[mer][++path2[mer][0]]=u; if (u==root) return; int i,ret; for (i=1;i<=N_N[u][0];i++){ ret = -(N_N[u][i]); if (ret > 0) expand_to_root(ret,mer); } } void remove_verbose_path(mer){ while(path[mer][--path[mer][0]]==path2[mer][--path2[mer][0]]); ++path[mer][0]; } void paytax(mer){ int j; for (j=1;j<=path[mer][0];j++){ taxsum+=(++tax[path[mer][j]]); } for (j=1;j<=path2[mer][0];j++){ taxsum+=(++tax[path2[mer][j]]); } } int main(){ int i,j,k, u,v,mer; scanf("%d",&number_of_nodes); for (i=1;i