Hello comunity:
I've been trying to solve the problem DISQUERY, and although I think my approach is correct I'm getting WA. Can somebody tell me what's wrong with this idea?
Since the traffic network is a tree, you can root that tree at any feasible node and apply the following algorithm: in a single BFS calculate the longest and the shortest road in the path from that root to all nodes, and set a discrete value for each node saying the height of that node in the tree. Let A and B be the nodes of the query, then if any of them has height 0, that node is the root and the information you need is already calculated, else walk up the tree from each node to the root keeping track the longest and the shortest road you have found in each travel. Clearly, those travels are going to converge to a particular node (the root of the subtree where A and B are placed), so when that node is found, all you have to do is determine the longest and shortest road of the two travels you have done, so let k be the convergence node and let's say we have made the travel from the lowest node (A for example), then l_query[k] has the value of the longest road from A to k, and s_query[k] has the shortest road from A to k, let v be any reachable node in the travel from B, if k is the next node in the travel from v, then the minimum road is the minimum among s_query[k], s_query[v] and d (d is the lenght of the road between v and k) and the situation is the same for maximum. Of course if A and B are directly conected (which means that A is parent of B or B is parent of A), the minimum and the maximum values are the road connecting them. I really think this idea is correct, so please help!
This is my code:
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 100000
#define MAXL 1000001
using namespace std;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
struct node {
int p, h, p_dist;
//p is the parent node, h is the height, p_dist is the distance to the parent;
vpii edg;
};
node nodes[MAXN+1];
int shortest[MAXN+1], longest[MAXN+1];
//length of the shortest and the longest road in the path from the root
int s_query[MAXN+1], l_query[MAXN+1];
int vis[MAXN+1];
void make_query(int a, int b, int& s, int& l, int query) {
if (nodes[a].h==0) {
s = shortest[b];
l = longest[b];
} else if (nodes[b].h==0) {
s = shortest[a];
l = longest[a];
} else if (nodes[b].p==a) {
s = l = nodes[b].p_dist;
} else if (nodes[a].p==b) {
s = l = nodes[a].p_dist;
} else {
if (nodes[a].h> nodes[b].h)
swap(a, b);
int k = b, q = a;
l_query[q] = 0;
s_query[q] = MAXL;
while (nodes[q].h!=0) {
l_query[nodes[q].p] = max(l_query[q], nodes[q].p_dist);
s_query[nodes[q].p] = min(s_query[q], nodes[q].p_dist);
vis[nodes[q].p] = query;
q = nodes[q].p;
}
l_query[k] = 0;
s_query[k] = MAXL;
while (nodes[k].h!=0) {
if (vis[nodes[k].p]==query) {
l = max(l_query[nodes[k].p], max(nodes[k].p_dist, l_query[k]));
s = min(s_query[nodes[k].p], min(nodes[k].p_dist, s_query[k]));
return;
} else {
l_query[nodes[k].p] = max(l_query[k], nodes[k].p_dist);
s_query[nodes[k].p] = min(s_query[k], nodes[k].p_dist);
k = nodes[k].p;
}
}
}
}
inline void bfs(int root) {
shortest[root] = MAXL;
longest[root] = 0;
queue<int> q;
q.push(root);
nodes[root].h = 0;
vis[root] = 1;
int u, v, i, d;
while (!q.empty()) {
u = q.front();
q.pop();
for (i = 0; i < (int)nodes[u].edg.size(); i++) {
v = nodes[u].edg[i].first;
if (!vis[v]) {
d = nodes[u].edg[i].second;
shortest[v] = min(shortest[u], d);
longest[v] = max(longest[u], d);
nodes[v].p = u;
nodes[v].p_dist = d;
nodes[v].h = nodes[u].h+1;
q.push(v);
vis[v] = 1;
}
}
}
}
int main() {
register int N, K, root, A, B, C, max_size = 0;
while (scanf("%d", &N)!=EOF) {
for (int i = 1; i <= N; i++)
nodes[i].edg.clear();
memset(vis, 0, sizeof(int)*(N+1));
for (register int i = 1; i < N; i++) {
scanf("%d %d %d", &A, &B, &C);
nodes[A].edg.push_back(make_pair(B, C));
nodes[B].edg.push_back(make_pair(A, C));
if ((int)nodes[A].edg.size() > max_size) {
root = A;
max_size = nodes[A].edg.size();
}
if ((int)nodes[B].edg.size() > max_size) {
root = B;
max_size = nodes[B].edg.size();
}
}
bfs(root);
memset(vis, 0, sizeof(int)*(N+1));
int max_p, min_p;
scanf("%d", &K);
for (register int i = 1; i <= K; i++) {
scanf("%d %d", &A, &B);
make_query(A, B, min_p, max_p, i);
printf("%d %d\n", min_p, max_p);
}
}
return 0;
}