16pts

#include<bits/stdc++.h>
using namespace std;
/*
题目大意：
给定了一颗含有n个节点的树，求树中两个节点s->t路径上途径的点（相邻两点最短距离不能超过k）的点权和最小值

解法1：只考虑k=1的情况，需要求出s->t路径上途径所有点的点权和的最小值
可以先预处理出根节点到树中第i个点路径上的点权和即sum[i]，然后找到s和t的最近公共祖先p
则最终结果为sum[s]+sum[t]-2*sum[p]+w[p]
*/
#define int long long
#define MAX_DEP 15
const int N = 2e5 + 10;
int n, q, k;
int w[N];//w[i]表示点i的权值
vector<int> g[N];//邻接表
int fa[N][16];//倍增法求LCA中要用到的fa数组，fa[x][i]表示从x向上走2^i到达的节点
int dep[N];//dep[i]表示i节点在树中的深度
int sum[N];//sum[i]表示根节点到树中第i个点路径上的点权和即sum[i]
//预处理fa、sum、dep数组
void dfs(int u, int f) {
	fa[u][0] = f;//初始化fa
	sum[u] = sum[f] + w[u];//计算sum数组
	dep[u] = dep[f] + 1;//计算dep数组
	//倍增法计算fa数组
	//从u向上走2^k可以分解为从u向上走2^(k-1)之后再走2^(k-1)
	for (int k = 1; k <= MAX_DEP; k++) 
		fa[u][k] = fa[fa[u][k - 1]][k - 1];
	//便利u节点的孩子继续向下处理
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (v == f) continue;//防止回搜
		dfs(v, u);
	}
}
//倍增求LCA，计算x,y的最近公共祖先
int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);//保证x的深度较大
	//优先跳x,先将x和y的深度调为一致
	for (int k = MAX_DEP; k >=0; k--) 
		if (dep[fa[x][k]] >= dep[y]) x = fa[x][k];
	//x和y深度一致时，如果两点重合，lca即为x或y
	if (x == y) return x;
	//若两点没有重合，则两点一起往上跳，直到相遇
	for (int k = MAX_DEP; k >= 0; k--) {
		if (fa[x][k] != fa[y][k]) {
			x = fa[x][k];
			y = fa[y][k];
		}
	}
	//相遇节点x/y即为最近公共祖先的孩子
	return fa[x][0];
}
signed main() {
	cin >> n >> q >> k;
	for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);

	for (int i = 1; i < n; i++) {
		int u, v;  scanf("%lld%lld", &u, &v);
		g[u].push_back(v);   g[v].push_back(u);
	}

	memset(dep, 0x3f, sizeof dep);
	sum[0] = 0, dep[0] = 0;//引入一个虚拟节点0
	dfs(1, 0);
	while (q--) {
		int s, t, p;
		scanf("%lld%lld", &s, &t);
		p = lca(s, t);
		printf("%lld\n", sum[s] + sum[t] - 2 * sum[p] + w[p]);
	}
	return 0;
}

44pts

#include<bits/stdc++.h>
using namespace std;
/*
题目大意：
给定了一颗含有n个节点的树，求树中两个节点s->t路径上途径的点（相邻两点最短距离不能超过k）的点权和最小值

解法1（LCA）：只考虑k=1的情况，需要求出s->t路径上途径所有点的点权和的最小值,16pts
可以先预处理出根节点到树中第i个点路径上的点权和即sum[i]，然后找到s和t的最近公共祖先p
则最终结果为sum[s]+sum[t]-2*sum[p]+w[p]

解法2（LCA+DP）：在k=1的基础上引入k=2的情况，对于k=2的情况我们考虑使用dp来处理-44pts
引入dp[i]，状态：dp[i]表示从起点（第1个点）到第i个点的权值和的最小值，对于k=1/k=2情况进行画图分析
得出结论，状态转移方程dp[i]=min(dp[i-1],dp[i-2])+w[i](其中i代表路径中点的序号，其中起点序号为1，x是序号为i-1节点的邻点)
*/
#define int long long
#define MAX_DEP 15
const int N = 2e5 + 10;
int n, q, k;
int w[N];//w[i]表示点i的权值
vector<int> g[N];//邻接表
int fa[N][16];//倍增法求LCA中要用到的fa数组，fa[x][i]表示从x向上走2^i到达的节点
int dep[N];//dep[i]表示i节点在树中的深度
int sum[N];//sum[i]表示根节点到树中第i个点路径上的点权和即sum[i]
int dp[N];//dp[i]表示从起点（第1个点）到第i个点的权值和的最小值
int id[N];//id[i]表示起点到终点路径上序号为i的点的对应的树节点编号
int cnt;//统计起点到终点路径上节点的数量
//预处理fa、sum、dep数组
void dfs(int u, int f) {
	fa[u][0] = f;//初始化fa
	sum[u] = sum[f] + w[u];//计算sum数组
	dep[u] = dep[f] + 1;//计算dep数组
	//倍增法计算fa数组
	//从u向上走2^k可以分解为从u向上走2^(k-1)之后再走2^(k-1)
	for (int k = 1; k <= MAX_DEP; k++) 
		fa[u][k] = fa[fa[u][k - 1]][k - 1];
	//便利u节点的孩子继续向下处理
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (v == f) continue;//防止回搜
		dfs(v, u);
	}
}
//倍增求LCA，计算x,y的最近公共祖先
int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);//保证x的深度较大
	//优先跳x,先将x和y的深度调为一致
	for (int k = MAX_DEP; k >=0; k--) 
		if (dep[fa[x][k]] >= dep[y]) x = fa[x][k];
	//x和y深度一致时，如果两点重合，lca即为x或y
	if (x == y) return x;
	//若两点没有重合，则两点一起往上跳，直到相遇
	for (int k = MAX_DEP; k >= 0; k--) {
		if (fa[x][k] != fa[y][k]) {
			x = fa[x][k];
			y = fa[y][k];
		}
	}
	//相遇节点x/y即为最近公共祖先的孩子
	return fa[x][0];
}
//处理起点到终点的cnt和id[]
void solve_stot(int s, int t, int p) {
	cnt = 0;
	for (int x = s; x != p; x = fa[x][0]) //从起点到最近公共祖先进行编号并处理id[]
		id[++cnt] = x;//建立路径中的序号和树节点编号的映射关系
	id[++cnt] = p;
	cnt = dep[s] + dep[t] - 2 * dep[p] + 1;//s->t的路径中节点数量
	for (int x = t; x != p; x = fa[x][0]) // 从终点到最近公共祖先进行编号并处理id[]
		id[cnt--] = x;
	cnt = dep[s] + dep[t] - 2 * dep[p] + 1;//s->t的路径中节点数量
}
int calc_min_dis() {
	fill(dp, dp + cnt + 1, 1e18);
	dp[1] = w[id[1]];//dp边界
	if (k == 2) 
		//遍历s->t路径中的序号i
		for (int i = 2; i <= cnt; i++) 
			dp[i] = min(dp[i - 1], dp[i - 2]) + w[id[i]];
	return dp[cnt];
}
signed main() {
	cin >> n >> q >> k;
	for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);

	for (int i = 1; i < n; i++) {
		int u, v;  scanf("%lld%lld", &u, &v);
		g[u].push_back(v);   g[v].push_back(u);
	}

	memset(dep, 0x3f, sizeof dep);
	sum[0] = 0, dep[0] = 0;//引入一个虚拟节点0
	dfs(1, 0);
	while (q--) {
		int s, t, p;
		scanf("%lld%lld", &s, &t);
		p = lca(s, t);
		if(k==1) printf("%lld\n", sum[s] + sum[t] - 2 * sum[p] + w[p]);
		else {
			solve_stot(s, t, p);
			printf("%lld\n", calc_min_dis());
		}
	}
	return 0;
}