i have the same problem with 3rd test.
But i use first DFS to find distance between root (0 node) and all another nodes. (N + N)
Then use LCA (N*LOG(N))
and eventually get TLE 3
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define RS(x,n) x.resize(n);
vector<int> used;
vector<int> tin;
vector<int> tout;
vector<vector<int> > up;
vector<int> dist;
struct edge
{
int value;
int vert;
edge(){};
edge(int v, int ve)
{
vert=v;
value = ve;
}
};
vector<vector<edge> > edges;
bool operator>(const edge & a,const edge & b)
{
return (a.value > b.value);
}
int n,m; // количество вершин и запросов
void input()
{
cin >> n;
int a,b,v;
edges.resize(n);
for(int i=0;i<n-1;i++)
{
cin >> a >> b >> v;
edges[a].push_back(edge(b,v));
edges[b].push_back(edge(a,v));
}
}
int maxValue = 1e9;
void deijkstra()
{
priority_queue<edge,vector<edge>,greater<edge> > p;
p.push(edge(0,0));
used.resize(n+1);
dist.assign(n+1,maxValue);
dist[0] = 0;
while(! p.empty())
{
edge cur = p.top(); p.pop();
if (used[cur.vert])
continue;
used[cur.vert] = 1;
for(int i = 0 ;i < edges[cur.vert].size();i++)
{
edge next = edges[cur.vert][i];
if (dist[next.vert] > dist[cur.vert] + next.value)
{
dist[next.vert] = dist[cur.vert] + next.value;
p.push(edge(next.vert,dist[next.vert]));
}
}
}
}
int l;
int timer;
bool upper(int a, int b)
{
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int LCA(int f, int s)
{
if (upper(f,s)) return f;
if (upper(s,f)) return s;
for(int i = l ; i >= 0; i--)
if (!upper(up[f][i],s))
f = up[f][i];
return up[f][0];
}
void dfs(int vert, int p = 0)
{
used[vert] = 1;
tin[vert] = ++ timer;
up[vert][0] = p;
for(int i=1;i<=l;i++)
up[vert][i] = up[up[vert][i-1]][i-1];
for(int i=0;i<edges[vert].size();i++)
{
int next = edges[vert][i].vert;
if (!used[next])
dfs(next,vert);
}
tout[vert] = ++ timer;
}
void prepare_lca()
{
tin.assign(n+1,0);
tout.assign(n+1,0);
up.resize(n+1);
used.assign(n+1,0);
while( (1 << l) <= n) l++;
//l++;
for(int i=0;i<n;i++)
RS(up[i],l+1);
dfs(0);
}
void find(int vert,int sum = 0)
{
used[vert] = 1;
dist[vert] = sum;
for(int i=0;i<edges[vert].size();i++)
{
edge next = edges[vert][i];
if (!used[next.vert])
find(next.vert,sum + next.value);
}
}
void solve()
{
//deijkstra();
used.assign(n+1,0);
dist.assign(n+1,maxValue);
dist[0] = 0;
find(0);
cin >> m;
int f,s;
prepare_lca();
for(int i=0;i<m;i++)
{
cin >> f >> s;
int lca = LCA(f,s);
cout << dist[f] + dist[s] - 2*dist[lca] << "\n";
}
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
input();
solve();
return 0;
}
If you use BFS for every query, the complexity is O(N*M) which is too big. I will give you some hints:
1) Root the tree(just make proper father-son relations)
2) Find the distance from the root node to the other nodes
3) Now for any 2 nodes x, y consider the node z, which is
their Least Common Ancestor, and how could this node help you
to find the distance between x and y.