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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
