FJUT 聪明的商人(树上倍增)题解

时间:2023-12-20 12:04:20

思路:求树上两点的距离,显然是dep[u] + dep[v] - 2 * dep[lca],用树上倍增去写。

参考:树上倍增的写法和应用(详细讲解,新手秒懂)

代码:

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
const int maxn = + ;
const int seed = ;
const ll MOD = 1e9 + ;
const ll INF = 1e17;
using namespace std;
struct Edge{
int to, next;
}edge[maxn << ];
int fa[maxn][], 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][] = pre;
for(int i = ; i <= maxf; i++){
if(fa[x][i - ] != -){
fa[x][i] = fa[fa[x][i - ]][i - ];
}
else break;
}
for(int i = head[x]; i != -; i = edge[i].next){
int v = edge[i].to;
if(v != pre){
dfs(v, x, deep + );
}
}
}
int LCA(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
int dis = dep[u] - dep[v];
for(int i = ; i <= maxf; i++){
if(( << i) & dis)
u = fa[u][i];
}
if(u == v) return u;
for(int i = maxf; i >= ; i--){
if(fa[u][i] != fa[v][i]){
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][];
} void init(){
maxf = ;
memset(head, -, sizeof(head));
memset(fa, -, sizeof(fa));
tot = ;
}
int main(){
int n, m, w; while(~scanf("%d%d%d", &n, &m, &w)){
init();
for(int i = ; i < n - ; i++){
int a, b;
scanf("%d%d", &a, &b);
addEdge(a, b);
addEdge(b, a);
}
dfs(, -, );
for(int i = ; 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] - * dep[lca];
if(v - dis * w >= ){
printf("%d\n", v - dis * w);
}
else{
printf("pass\n");
}
}
}
return ;
}