题目连接：http://acm.uestc.edu.cn/#/problem/show/92
题意：给定一棵树，最后给加一条边，给定Q次查询，每次查询加上最后一条边之后是否比不加这条边要近，如果近的话，输出近多少，否则输出0
思路：没加最后一条边之前两点之间的距离是dis(u) + dis(v) - 2*dis(lca(u, v)); 加上之后就是必须要经过这两个点。(假设最后添加的一条边的端点为x和y，权值为w)min(dis(u, x) + dis(v, y) + w, dis(u, y) + dis(v, x) + w)
代码如下：
/*************************************************************************
> File Name: 4.cpp
> Author: Howe_Young
> Mail: 1013410795@qq.com
> Created Time: 2015年10月08日 星期四 19时53分38秒
************************************************************************/ #include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm> using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
struct Edge {
int to, next, w;
}edge[maxn<<];
int tot, head[maxn];
int cnt;
int Euler[maxn<<];
int R[maxn];
int dis[maxn<<];
int dep[maxn<<];
int dp[maxn<<][];
void init()
{
cnt = ;
tot = ;
memset(head, -, sizeof(head));
}
void addedge(int u, int v, int w)
{
edge[tot].to = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u, int fa, int depth, int dist)
{
Euler[++cnt] = u;
R[u] = cnt;
dep[cnt] = depth;
dis[cnt] = dist;
for (int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if (v == fa) continue;
dfs(v, u, depth + , dist + edge[i].w);
Euler[++cnt] = u;
dep[cnt] = depth;
dis[cnt] = dist;
}
} void RMQ(int n)
{
for (int i = ; i <= n; i++) dp[i][] = i;
int m = log2(n);
for (int j = ; j <= m; j++)
for (int i = ; i + ( << j) - <= n; i++)
dp[i][j] = dep[dp[i][j - ]] < dep[dp[i + ( << (j - ))][j - ]] ? dp[i][j - ] : dp[i + ( << (j - ))][j - ];
}
int getLCA(int u, int v)
{
if (u == v) return v;
int l = R[u], r = R[v];
if (l > r) swap(l, r);
int k = log2(r - l + );
int lca = dep[dp[l][k]] < dep[dp[r - ( << k) + ][k]] ? dp[l][k] : dp[r - ( << k) + ][k];
return Euler[lca];
}
int getdist(int u, int v)
{
if (u == v) return ;
int l = R[u], r = R[v];
int lca = getLCA(u, v);
return dis[l] + dis[r] - * dis[R[lca]];
}
int main()
{
int T, kase = ;
scanf("%d", &T);
while (T--)
{
init();
int n, Q;
int u, v, w;
scanf("%d %d", &n, &Q);
for (int i = ; i < n; i++)
{
scanf("%d %d %d", &u, &v, &w);
addedge(u, v, w);
addedge(v, u, w);
}
scanf("%d %d %d", &u, &v, &w);
dfs(, , , );
RMQ(cnt);
printf("Case #%d:\n", ++kase);
while (Q--)
{
int a, b;
scanf("%d %d", &a, &b);
int dis1 = getdist(a, b);
int dis2 = min(getdist(a, u) + getdist(v, b) + w, getdist(a, v) + getdist(u, b) + w);
if (dis1 > dis2)
printf("%d\n", dis1 - dis2);
else
printf("0\n");
}
}
return ;
}