Can someone tell me how to solve this problem:

There are N(N<=50000) cities. And there are N-1 roads between them. It is always possible to get from one city to another (so it is a tree). Then N-1 roads are described with three integers 1<=A[i],B[i]<=N and 1<=time[i]<=1000 meaning that a road between cities A[i] and B[i] can be travelled in time[i] hours. Then there are M (1<=M<=50000) queries to answer. Each query contains a pair of numbers 1<=X,Y<=N. It is necessary to find the time needed to pass from city X to city Y. Output should contain M lines - answers to the queries.

Time Limit: 4 sec.
Memory Limit: 32 MB.

PS. Sorry for my poor English.

Use LCA algorithm. ( Least Common Ancestor )
O( NlogN + M )
You can search this algo in the internet.

Thanks!
 I'll try to find this algo in internet.
 Can you give a link, where this algo is explained in russian?

Sorry , I can't help you.
I only know this in English.

wrong