::::info[这是倍增LCA的代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

namespace fastIO {//吾常于「oi-wiki」习，自悟「快读快写」之术。
	template<typename T>inline void r(T& a) { a = 0; char ch = gc(); bool ok = 0; for (; ch < '0' || ch>'9';)ok ^= (ch == '-'), ch = gc(); for (; ch >= '0' && ch <= '9';)a = (a << 1) + (a << 3) + (ch ^ 48), ch = gc(); if (ok)a = -a; }
	template<typename T>inline void w(T a) { if (a == 0) { pc('0'); return; }static char ch[20]; int till = 0; if (a < 0) { pc('-'); for (; a;)ch[till++] = -(a % 10), a /= 10; } else for (; a;)ch[till++] = a % 10, a /= 10; for (; till;)pc(ch[--till] ^ 48); }
	struct FIstream { inline FIstream operator>>(int& a) { r(a); return{}; } }in;
	struct FOstream {
		inline FOstream operator<<(const int a) { w(a); return{}; }
		inline FOstream operator<<(const char ch) { pc(ch); return{}; }
		inline FOstream operator<<(const string s) { for (int i = 0; i < s.size(); i++)pc(s[i]); return{}; }
	}out;
}using fastIO::in; using fastIO::out;
#define N 100005
vector<int>e[N];
int a[N], ans[N], as[N];
int tmp[N];
struct Node {
	int id, l, r, sign; // 查询ID、离散化区间、符号(+1/-1)
};
vector<Node> nd[N];
struct tree {
	int c[N + 50];
	int n;
	void init(int size) {
		n = size;
		memset(c, 0, sizeof(c));
	}
	void add(int x, int w, int v) {
		for (; x <= n; x += x & -x) c[x] += v;
	}
	int Sum(int x) {
		int res = 0;
		for (; x; x -= x & -x) res += c[x];
		return res;
	}
	int sum(int l, int r) {
		return Sum(r) - Sum(l - 1);
	}
} t;
int f[500005][25];
int d[500005];

void dfs(int x, int fa) {
	d[x] = d[fa] + 1;
	f[x][0] = fa;
	for (auto i : e[x]) {
		if (i == fa)continue;
		dfs(i, x);
	}
}

int lca(int x, int y) {
	if (d[x] < d[y])swap(x, y);
	for (int i = 19; i >= 0; i--)if (d[f[x][i]] >= d[y])x = f[x][i];
	if (x == y)return x;
	for (int i = 19; i >= 0; i--)
		if (f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}
void dfss(int x, int fa) {
	t.add(as[x], as[x], a[x]);
	for (auto i : nd[x]) {
		ans[i.id] += t.sum(i.l, i.r) * i.sign;
	}
	for (auto i : e[x]) {
		if (i == fa)continue;
		dfss(i, x);
	}
	t.add(as[x], as[x], -a[x]);
}

void Main() {
	int n, m;
	for (; cin >> n >> m;) {
		for (int i = 1; i <= n; i++) {
			e[i].clear();
			nd[i].clear();
		}
		for (int i = 1; i <= m; i++)
			ans[i] = 0;
		int till = 0;
		for (int i = 1; i <= n; i++) {
			in >> a[i];
			tmp[++till] = a[i];
		}
		for (int i = 1; i < n; i++) {
			int x, y; in >> x >> y;
			e[x].push_back(y);
			e[y].push_back(x);
		}
		sort(tmp + 1, tmp + 1 + n);
		till = unique(tmp + 1, tmp + 1 + n) - tmp - 1;
		for (int i = 1; i <= n; i++)
			as[i] = lower_bound(tmp + 1, tmp + 1 + till, a[i]) - tmp;
		t.init(till + 10);
		dfs(1,0);
		for (int i = 1; (1 << i) <= n; i++)
			for (int j = 1; j <= n; j++)
				f[j][i] = f[f[j][i - 1]][i - 1];
		for (int i = 1; i <= m; i++) {
			int s, t, a, b;
			in >> s >> t >> a >> b;
			int l = lower_bound(tmp + 1, tmp + 1 + till, a) - tmp;
			int r = upper_bound(tmp + 1, tmp + 1 + till, b) - tmp - 1;
			int z = lca(t, s);
			nd[s].push_back({ i, l, r, 1 });
			nd[t].push_back({ i, l, r, 1 });
			nd[z].push_back({ i, l, r, -1 });
			if (f[z]) nd[f[z][0]].push_back({ i, l, r, -1 });
		}
		dfss(1, 0);
		for (int i = 1; i <= m; i++)out << ans[i] << " ";
		out << '\n';
	}
}
signed main() { Main(); return 0; }

:::: ::::info[这是树剖LCA的代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

namespace fastIO {//吾常于「oi-wiki」习，自悟「快读快写」之术。
	template<typename T>inline void r(T& a) { a = 0; char ch = gc(); bool ok = 0; for (; ch < '0' || ch>'9';)ok ^= (ch == '-'), ch = gc(); for (; ch >= '0' && ch <= '9';)a = (a << 1) + (a << 3) + (ch ^ 48), ch = gc(); if (ok)a = -a; }
	template<typename T>inline void w(T a) { if (a == 0) { pc('0'); return; }static char ch[20]; int till = 0; if (a < 0) { pc('-'); for (; a;)ch[till++] = -(a % 10), a /= 10; } else for (; a;)ch[till++] = a % 10, a /= 10; for (; till;)pc(ch[--till] ^ 48); }
	struct FIstream { inline FIstream operator>>(int& a) { r(a); return{}; } }in;
	struct FOstream {
		inline FOstream operator<<(const int a) { w(a); return{}; }
		inline FOstream operator<<(const char ch) { pc(ch); return{}; }
		inline FOstream operator<<(const string s) { for (int i = 0; i < s.size(); i++)pc(s[i]); return{}; }
	}out;
}using fastIO::in; using fastIO::out;
#define N 100005
vector<int>e[N];
int dep[N], f[N], ns[N], siz[N], top[N], a[N], ans[N], as[N];
int tmp[N];
struct Node {
	int id, l, r, sign; // 查询ID、离散化区间、符号(+1/-1)
};
vector<Node> nd[N];
struct tree {
	int c[N + 50];
	int n;
	void init(int size) {
		n = size;
		memset(c, 0, sizeof(c));
	}
	void add(int x, int w, int v) {
		for (; x <= n; x += x & -x) c[x] += v;
	}
	int Sum(int x) {
		int res = 0;
		for (; x; x -= x & -x) res += c[x];
		return res;
	}
	int sum(int l, int r) {
		return Sum(r) - Sum(l - 1);
	}
} t;
void dfs(int x, int fa) {
	f[x] = fa; int k = -1; siz[x] = 1;
	dep[x] = dep[fa] + 1;
	for (auto i : e[x]) {
		if (i == fa)continue;
		dfs(i, x); siz[x] += siz[i];
		if (k < siz[i])k = siz[i]; ns[x] = i;
	}
}
void dfs2(int x, int fa) {
	if (ns[x]) {
		top[ns[x]] = top[x];
		dfs2(ns[x], x);
	}
	for (auto i : e[x]) {
		if (i == fa || i == ns[x])continue;
		top[i] = i;
		dfs2(i, x);
	}
}
int lca(int x, int y) {
	for (; top[x] != top[y];) {
		if (dep[top[x]] < dep[top[y]])swap(x, y);
		x = f[top[x]];
	}
	return (dep[x] < dep[y] ? x : y);
}
void dfss(int x, int fa) {
	t.add(as[x], as[x], a[x]);
	for (auto i : nd[x]) {
		ans[i.id] += t.sum(i.l, i.r) * i.sign;
	}
	for (auto i : e[x]) {
		if (i == fa)continue;
		dfss(i, x);
	}
	t.add(as[x], as[x], -a[x]);
}

void Main() {
	int n, m;
	for (; cin >> n >> m;) {
		memset(ns, 0, sizeof(ns));
		for (int i = 1; i <= n; i++) {
			e[i].clear();
			nd[i].clear();
		}
		for (int i = 1; i <= m; i++)
			ans[i] = 0;
		int till = 0;
		for (int i = 1; i <= n; i++) {
			in >> a[i];
			tmp[++till] = a[i];
		}
		for (int i = 1; i < n; i++) {
			int x, y; in >> x >> y;
			e[x].push_back(y);
			e[y].push_back(x);
		}
		sort(tmp + 1, tmp + 1 + n);
		till = unique(tmp + 1, tmp + 1 + n) - tmp - 1;
		for (int i = 1; i <= n; i++)
			as[i] = lower_bound(tmp + 1, tmp + 1 + till, a[i]) - tmp;
		t.init(till + 10);
		top[1] = 1;
		dfs(1, 0); dfs2(1, 0);
		for (int i = 1; i <= m; i++) {
			int s, t, a, b;
			in >> s >> t >> a >> b;
			int l = lower_bound(tmp + 1, tmp + 1 + till, a) - tmp;
			int r = upper_bound(tmp + 1, tmp + 1 + till, b) - tmp - 1;
			int z = lca(1, s);
			nd[s].push_back({ i, l, r, 1 });
			nd[t].push_back({ i, l, r, 1 });
			nd[z].push_back({ i, l, r, -1 });
			if (f[z]) nd[f[z]].push_back({ i, l, r, -1 });
		}
		dfss(1, 0);
		for (int i = 1; i <= m; i++)out << ans[i] << " ";
		out << '\n';
		return;
	}
}
signed main() { Main(); return 0; }

:::: 两份代码仅有求LCA的方式不同，为什么前者AC而后者TLE？

::::info[附题目] ::::