#include #include typedef struct directedGraph{ int *vertex; int *next; int *start; int v,e; int pointer; } graph; graph* newGraph(const int v,const int e){ graph *g=(graph *)malloc(sizeof(graph)); g->vertex=(int *)calloc(e,sizeof(int)); g->next=(int *)calloc(e,sizeof(int)); g->start=(int *)calloc(v,sizeof(int)); for(int i=0;istart[i]=-1; g->v=v; g->e=e; g->pointer=0; return g; } void freeGraph(graph *g){ free(g->vertex); free(g->next); free(g->start); free(g); return; } void addEdge(graph *g,const int from,const int to){ const int p=g->pointer; g->vertex[p]=to; g->next[p]=g->start[from]; g->start[from]=p; g->pointer++; return; } typedef long long int int64; void add(int *bit,int index,int v){ index++; const int n=bit[0]; for(int i=index;i<=n;i+=i&-i) bit[i]+=v; } int sum(int *bit,int index){ index++; int res=0; for(int i=index;i>0;i-=i&-i) res+=bit[i]; return res; } int64 calc(int v,int *bit,graph *g,int *used){ if(used[v]) return 0; used[v]=1; int64 res=sum(bit,v); add(bit,v,1); for(int p=g->start[v];p!=-1;p=g->next[p]){ int u=g->vertex[p]; res+=calc(u,bit,g,used); } add(bit,v,-1); return res; } void run(void){ int n; scanf("%d",&n); graph *g=newGraph(n,2*n); int i; for(i=1;i