I have solved the last one :) how can i solve this one: http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4805
using LCA, I used this algorithm: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor but i dont know how to "count the weights of the edges". I have this code that prints the Lowest Common Ancestor: #include <iostream> #include <stdio.h> using namespace std; #define MAXN 100002 int P[MAXN][20];//parent 16=log(MAXN) int T[MAXN];//first parent int L[MAXN];//level int C[MAXN];//weight of edges int query(int p, int q){ int tmp,log,i,c=0; //if p is situated on a higher level than q then we swap them if(L[p]<L[q]) swap(p,q); //we compute the value of [log(L[p)] for(log=1;1<<log<=L[p];++log); log--; //we find the ancestor of node p situated on the same level //with q using the values in P for(i=log;i>=0;--i) if(L[p]-(1<<i)>=L[q]) p=P[p][i]; if(p==q) return p; //we compute LCA(p, q) using the values in 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(){ //freopen("1.txt","r",stdin); int n,i,j,a,b,q; T[0]=P[0][0]=0; while(cin>>n && n){ //preprocess; 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;//level C[i]=b;//weight } 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;//queries for(i=0;i<q;i++){ if(i) cout<<" "; cin>>a>>b; cout<<query(a,b); } cout<<endl; } } please, Thanks in advance. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
