[algogeeks] Correctness of an algorithm

[rgap]

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.