plz, help me! why i get crash(access violation).
// LCA (least common ancestor) offline by using interval tree in O(logN)
// Solution by Serekov Abzal
#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
int ADD = 65536;
int inf = 9999999;
vector <vector <pair<int, int> > > graph;
vector <bool> b(50001, false);
vector <int> h(50001, 0);
vector <int> order;
vector <int> d(50001, 0);
vector <int> first(50001, -1);
pair <int, int> tree[2 * 65536 + 1];
int n, root = 0;
void init_graph()
{
scanf("%d", &n);
graph.resize(n);
for (int i = 0; i < n - 1; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
graph[u].push_back(make_pair(v, w));
graph[v].push_back(make_pair(u, w));
}
};
void dfs(int v, int p)
{
b[v] = true;
h[v] = p;
order.push_back(v);
for (int i = 0; i < graph[v].size(); i++)
if (!b[graph[v][i].first])
{
dfs(graph[v][i].first, p + 1);
order.push_back(v);
}
};
void bfs(int v)
{
queue <int> Q;
Q.push(v);
while (!Q.empty())
{
int u = Q.front();
b[u] = true;
for (int i = 0; i < graph[u].size(); i++)
if (!b[graph[u][i].first])
{
d[graph[u][i].first] = d[u] + graph[u][i].second;
Q.push(graph[u][i].first);
}
Q.pop();
}
};
void prepare()
{
h[root] = 0;
dfs(root, 0);
for (int i = 0; i < order.size(); i++)
if (first[order[i]] == -1)
first[order[i]] = i;
for (int i = 0; i < n; i++) b[i] = false;
d[root] = 0;
bfs(root);
};
int minimum(int u, int v)
{
int l = u, r = v, ans = inf, ver = inf;
while (l <= r)
{
if (l % 2 == 1)
{
if (tree[l].second < ans)
{
ans = tree[l].second;
ver = tree[l].first;
}
l++;
};
if (r % 2 == 0)
{
if (tree[r].second < ans)
{
ans = tree[r].second;
ver = tree[r].first;
}
--r;
}
l/=2; r/=2;
}
return ver;
};
int lca(int u, int v)
{
int l = first[u] + ADD, r = first[v] + ADD;
return minimum(l, r);
};
void init_zaprosi()
{
int m;
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
int ans = d[u] + d[v] - 2 * d[lca(u, v)];
printf("%d\n", ans);
}
};
void tree_build()
{
for (int i = 0; i <= 2 * ADD; i++)
tree[i] = make_pair(-1, inf);
for (int i = ADD; i < ADD + order.size(); i++)
{
tree[i].first = order[i - ADD];
tree[i].second = h[order[i - ADD]];
}
for (int i = ADD - 1; i > 0; i--)
{
if (tree[2 * i].first == -1 || tree[2 * i + 1].first == -1)
{
if (!(tree[2 * i].first == -1 && tree[2 * i + 1].first == -1))
{
if (tree[2 * i].first == -1) tree[i] = tree[2 * i + 1]; else tree[i] = tree[2 * i];
}
}
else
{
if (tree[2 * i].second < tree[2 * i + 1].second) tree[i] = tree[2 * i]; else tree[i] = tree[2 * i + 1];
}
}
};
int main()
{
init_graph();
prepare();
tree_build();
init_zaprosi();
return 0;
}
