本文共 1690 字，大约阅读时间需要 5 分钟。
思路：求树上两点的距离，显然是dep[u] + dep[v] - 2 * dep[lca]，用树上倍增去写。
参考：
代码：
#include #include #include #include #include #include #include #include #include #include typedef long long ll;const int maxn = 50000 + 10;const int seed = 131;const ll MOD = 1e9 + 7;const ll INF = 1e17;using namespace std;struct Edge{ int to, next;}edge[maxn << 2];int fa[maxn][100], dep[maxn], head[maxn], tot, maxf;void addEdge(int u, int v){ edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;}void dfs(int x, int pre, int deep){ dep[x] = deep; fa[x][0] = pre; for(int i = 1; i <= maxf; i++){ if(fa[x][i - 1] != -1){ fa[x][i] = fa[fa[x][i - 1]][i - 1]; } else break; } for(int i = head[x]; i != -1; i = edge[i].next){ int v = edge[i].to; if(v != pre){ dfs(v, x, deep + 1); } }}int LCA(int u, int v){ if(dep[u] < dep[v]) swap(u, v); int dis = dep[u] - dep[v]; for(int i = 0; i <= maxf; i++){ if((1 << i) & dis) u = fa[u][i]; } if(u == v) return u; for(int i = maxf; i >= 0; i--){ if(fa[u][i] != fa[v][i]){ u = fa[u][i]; v = fa[v][i]; } } return fa[u][0];}void init(){ maxf = 30; memset(head, -1, sizeof(head)); memset(fa, -1, sizeof(fa)); tot = 0;}int main(){ int n, m, w; while(~scanf("%d%d%d", &n, &m, &w)){ init(); for(int i = 0; i < n - 1; i++){ int a, b; scanf("%d%d", &a, &b); addEdge(a, b); addEdge(b, a); } dfs(0, -1, 0); for(int i = 0; i < m; i++){ int p, q, v; scanf("%d%d%d", &p, &q, &v); int lca = LCA(p , q); int dis = dep[p] + dep[q] - 2 * dep[lca]; if(v - dis * w >= 0){ printf("%d\n", v - dis * w); } else{ printf("pass\n"); } } } return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/9937648.html