please, how can i prove the correctness of an algorithm, for example this one:
#include <iostream> #include <algorithm> #include <stdio.h> using namespace std; #define MAXN 100002 int P[MAXN][20]; int T[MAXN]; int L[MAXN]; long long int C[MAXN]; int query(int p, int q){//lca int tmp,log,i,c=0; if(L[p]<L[q]) swap(p,q); for(log=1;1<<log<=L[p];++log); log--; for(i=log;i>=0;--i) if(L[p]-(1<<i)>=L[q]) p=P[p][i]; if(p==q) return p; for(i=log;i>=0;--i){ if(P[p][i]!=-1 && P[p][i]!=P[q][i]){ p=P[p][i]; q=P[q][i]; } } return T[p]; } int main(){ int n,i,j,a,q; long long int b; T[0]=P[0][0]=0; while(cin>>n && n){ for(i=1;i<n;++i) for(j=1;1<<j<n;++j) P[i][j]=-1; for(i=1;i<n;++i){ cin>>a>>b; T[i]=P[i][0]=a; L[i]=L[a]+1; C[i]=b+C[a]; } for(j=1;1<<j<n;++j){ for(i=0;i<n;++i){ if(P[i][j-1]!=-1) P[i][j]=P[P[i][j-1]][j-1]; } } cin>>q; for(i=0;i<q;i++){ if(i) cout<<" "; cin>>a>>b; cout<<C[a]+C[b]-2*C[query(a,b)]; } cout<<endl; } } maybe using induction? please... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.