Description
Bob has traveled to byteland, he find the N cities in byteland formed a tree structure, a tree structure is very special structure, there is exactly one path connecting each pair of nodes, and a tree with N nodes has N - 1 edges.
As a traveler, Bob wants to journey between those N cities, and he know the time each road will cost. he advises the king of byteland building a new road to save time, and then, a new road was built. Now Bob has Q journey plan, give you the start city and destination city, please tell Bob how many time is saved by add a road if he always choose the shortest path. Note that if it's better not journey from the new roads,
the answer is 0.
Input
First line of the input is a single integer T(1 <= T <= 20), indicating there are T test cases.
For each test case, the first will line contain two integers N(2 <= N <= 10^5) and Q(1 <= Q <= 10^5), indicating the number of cities in byteland and the journey plans. Then N line followed, each line will contain three integer x, y(1 <= x,y <= N) and z(1 <= z <= 1000) indicating there is a road cost z time connect the x-th city and the y-th city, the first N - 1 roads will form a tree structure, indicating the original roads, and the N-th line is the road built after Bob advised the king. Then Q line followed, each line will contain two integer x and y(1 <= x,y <= N), indicating there is a journey plan from the x-th city to y-th city.
Output
For each case, you should first output "Case #t:" in a single line, where t indicating the case number between 1 and T, then Q lines followed, the i-th line contains one integer indicating the time could saved in i-th journey plan.
题目大意：给一棵树T，每条边都有一个权值，然后又一条新增边，多次询问：从点x到点y在T上走的最短距离，在加上那条新增边之后，最短距离可以减少多少。
思路：任意确定一个根root，DFS计算每个点到根的距离dis[]，然后每两点间的最短距离为dis[x]+dis[y]-2*dis[LCA(x,y)]。若新加入一条边u--v，那么如果我们必须经过u--v，那么从x到y的最短距离就为dis(x,u)+dis(u,v)+dis(v,y)或dis(x,v)+dis(v,u)+dis(u,y)。这样在线处理答案就行。
PS：至于求LCA的方法可以参考2007年郭华阳的论文《RMQ&LCA问题》，RMQ可以用ST算法，至于那个O(n)的±1RMQ有空再写把……
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int MAXN = ;
const int MAXM = MAXN * ; int head[MAXN];
int next[MAXM], to[MAXM], cost[MAXM];
int ecnt, root; void init() {
ecnt = ;
memset(head, , sizeof(head));
} void addEdge(int u, int v, int c) {
to[ecnt] = v; cost[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++;
to[ecnt] = u; cost[ecnt] = c; next[ecnt] = head[v]; head[v] = ecnt++;
} int dis[MAXN]; void dfs(int f, int u, int di) {
dis[u] = di;
for(int p = head[u]; p; p = next[p]) {
if(to[p] == f) continue;
dfs(u, to[p], di + cost[p]);
}
} int RMQ[*MAXN], mm[*MAXN], best[][*MAXN]; void initMM() {
mm[] = -;
for(int i = ; i <= MAXN * - ; ++i)
mm[i] = ((i&(i-)) == ) ? mm[i-] + : mm[i-];
} void initRMQ(int n) {
int i, j, a, b;
for(i = ; i <= n; ++i) best[][i] = i;
for(i = ; i <= mm[n]; ++i) {
for(j = ; j <= n + - ( << i); ++j) {
a = best[i - ][j];
b = best[i - ][j + ( << (i - ))];
if(RMQ[a] < RMQ[b]) best[i][j] = a;
else best[i][j] = b;
}
}
} int askRMQ(int a,int b) {
int t;
t = mm[b - a + ]; b -= ( << t)-;
a = best[t][a]; b = best[t][b];
return RMQ[a] < RMQ[b] ? a : b;
} int dfs_clock, num[*MAXN], pos[MAXN];//LCA void dfs_LCA(int f, int u, int dep) {
pos[u] = ++dfs_clock;
RMQ[dfs_clock] = dep; num[dfs_clock] = u;
for(int p = head[u]; p; p = next[p]) {
if(to[p] == f) continue;
dfs_LCA(u, to[p], dep + );
++dfs_clock;
RMQ[dfs_clock] = dep; num[dfs_clock] = u;
}
} int LCA(int u, int v) {
if(pos[u] > pos[v]) swap(u, v);
return num[askRMQ(pos[u], pos[v])];
} void initLCA(int n) {
dfs_clock = ;
dfs_LCA(, root, );
initRMQ(dfs_clock);
} int mindis(int x, int y) {
return dis[x] + dis[y] - * dis[LCA(x, y)];
} int main() {
int T, n, Q;
int x, y, z, p;
int u, v;
initMM();
scanf("%d", &T);
for(int t = ; t <= T; ++t) {
printf("Case #%d:\n", t);
scanf("%d%d", &n, &Q);
init();
for(int i = ; i < n - ; ++i) {
scanf("%d%d%d", &x, &y, &z);
addEdge(x, y, z);
}
scanf("%d%d%d", &x, &y, &z);
root = x;
dis[root] = ;
for(p = head[root]; p; p = next[p]) dfs(root, to[p], cost[p]);
initLCA(n);
while(Q--) {
scanf("%d%d", &u, &v);
int ans1 = mindis(u, v);
int ans2 = min(mindis(u, x) + mindis(y, v), mindis(u, y) + mindis(x, v)) + z;
if(ans1 > ans2) printf("%d\n", ans1 - ans2);
else printf("0\n");
}
}
}