|
eof(head));
for(int i = 1; i <= M; i++) {
int x = read(), y = read(), z = read();
AddEdge(x, y, z); AddEdge(y, x, z);
}
Tarjan(1, 0); dis[1] = 0; deep[1] = 1;
//for(int i = 1; i <= N; i++) printf("%d ", dfn[i]); puts("");
//for(int i = 1; i <= N; i++) printf("%d ", vec[i].size()); puts("");
//printf("%d\n", tot);
dfs1(1, 0);
dfs2(1, 1);
//for(int i = 1; i <= tot; i++) printf("%d ", top[i]); puts("");
while(Q--) {
int x = read(), y = read();
int lca = LCA(x, y);
if(lca <= N) {printf("%d\n", dis[x] + dis[y] - (dis[lca] << 1)); continue;}
int p1 = Jump(x, lca);
int p2 = Jump(y, lca);
int ans = dis[x] - dis[p1] + dis[y] - dis[p2] + min(abs(cdis[p2] - cdis[p1]),
cdis[lca] - abs(cdis[p2] - cdis[p1]));
printf("%d\n", ans);
}
return 0;
}
|