here is my program it works right on the first test on my PC but here it fails!!! I even don't know what's the problem.
I hope that the first test is the same as in the text, otherwise there's really something wrong with the pro.
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
#define MaxN 50010
#define MaxLogN 20
#define MaxM 75010
vector< pair<int,int> > list[MaxN];
int pr1[MaxN][MaxLogN]; //array of 2^i -th ancestor with the cost
int pr2[MaxN][MaxLogN];
int tin[MaxN];
int tout[MaxN];
int used[MaxN];
int l=MaxLogN;
int timer=0;
void dfs(int v, int p, int cost)
{
used[v]=1;
tin[v]=timer;
timer++;
pr1[v][0]=p;
pr2[v][0]=cost;
for(int i=1; i<l; i++)
{
pr1[v][i]=pr1[pr1[v][i-1]][i-1];
pr2[v][i]=pr2[v][i-1] + pr2[pr1[v][i-1]][i-1];
}
for(int i=0; i<list[v].size(); i++)
{
if(used[list[v][i].first]==0)
dfs(list[v][i].first,v,list[v][i].second);
}
tout[v]=timer;
timer++;
}
int upper(int a,int b)
{
if(tin[a]<=tin[b] && tout[b]<=tout[a]) return 1;
return 0;
}
int lca(int a,int b)
{
//a - ancestor
if(upper(a,b)==1)
{
int i=0;
while(upper(pr1[b][i],a)==0 && i<l) i++;
i--;
if(pr1[b][i+1]==a) return pr2[b][i+1];
return pr2[b][i]+lca(a,pr1[b][i]);
}
//b - ancestor
if(upper(b,a)==1)
return lca(b,a);
for(int i=0; i<l; i++)
{
if(upper(pr1[a][i],b)==1)
{
if(i==0)
return pr2[a][i]+lca(pr1[a][i],b);
return(pr2[a][i-1]+lca(pr1[a][i-1],b));
}
}
}
int main()
{
memset(used,0,MaxN*sizeof(used[0]));
memset(pr1,0,MaxN*MaxLogN*sizeof(pr1[0][0]));
memset(pr2,0,MaxN*MaxLogN*sizeof(pr2[0][0]));
/*freopen("INPUT.txt","r",stdin);
freopen("OUTPUT.txt","w",stdout);*/
int n,m;
cin>>n;
for(int i=0; i<n-1; i++)
{
int a,b,w;
cin>>a>>b>>w;
list[a].push_back(make_pair(b,w));
list[b].push_back(make_pair(a,w));
}
dfs(0,0,0);
cin>>m;
int ans[MaxM];
for(int i=0; i<m; i++)
{
int a,b;
cin>>a>>b;
ans[i]=lca(a,b);
}
for(int i=0; i<m-1; i++)
cout<<ans[i]<<"\n";
cout<<ans[m-1];
}
