Hướng dẫn cho LQDOJ CUP 2022 - Round 8 - MEETING
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask \(1\) (\(10\%\) số điểm): \(n,q \leq 100\).
Tutorial
Ta nhận xét rằng tọa độ \(S(x_S, y_S)\) cần tìm sẽ thỏa mãn \(\exists i \in [1,n] : x_i = x_S\) và \(\exists j \in [1,n] : y_j = y_S\).
Với \(n, q\) nhỏ, ta chỉ duyệt qua tất cả các cặp giá trị \((x_i, y_j)\).
Độ phức tạp: \(\mathcal{O}(q \times n^3)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50005;
const long long INF = (long long)1e18 + 10;
struct Point {
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
friend int dist(const Point &A, const Point &B) {
return abs(A.x - B.x) + abs(A.y - B.y);
}
};
int n, numQuery;
vector<int> adj[MAX_N];
int depth[MAX_N], parent[MAX_N];
Point point[MAX_N], tmp[MAX_N];
void dfs(int node) {
for (int u : adj[node]) {
if (u != parent[node]) {
depth[u] = depth[node] + 1;
parent[u] = node;
dfs(u);
}
}
}
long long query(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
int dem = 0;
while (depth[u] > depth[v]) {
tmp[++dem] = point[u];
u = parent[u];
}
while (u != v) {
tmp[++dem] = point[u];
tmp[++dem] = point[v];
u = parent[u];
v = parent[v];
}
tmp[++dem] = point[u];
long long result = INF;
for (int idx = 1; idx <= dem; ++idx) {
for (int idy = 1; idy <= dem; ++idy) {
Point S(tmp[idx].x, tmp[idy].y);
long long sum = 0;
for (int i = 1; i <= dem; ++i) {
sum += dist(S, tmp[i]);
}
result = min(result, sum);
}
}
return result;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("MEETING.inp", "r", stdin);
freopen("MEETING.out", "w", stdout);
cin >> n >> numQuery;
for (int i = 1; i <= n; ++i) {
cin >> point[i].x;
}
for (int i = 1; i <= n; ++i) {
cin >> point[i].y;
}
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
for (int i = 1; i <= numQuery; ++i) {
int u, v;
cin >> u >> v;
cout << query(u, v) << "\n";
}
return 0;
}
Phân tích yêu cầu đề bài
Bài toán con
Cho \(n\) điểm \((x_i, y_i)\). Tìm điểm \(S(x_S, y_S)\) sao cho \(\sum_{i = 1}^{n} [|x_S - x_i| + |y_S - y_i|]\) là cực tiểu.
Ta có thể khai triển biểu thức trên thành \(\sum_{i=1}^{n}|x_S-x_i| + \sum_{i=1}^{n}|y_S-y_i|\).
Từ đây, ta đưa bài toán về bài toán tổng quát hơn như sau: Cho dãy gồm \(n\) số \(a_i\), tìm giá trị \(p\) sao cho \(\sum_{i = 1}^{n}|p - a_i|\) cực tiểu.
Đây là một bài toán có thể gọi là kinh điển với lời giải là chọn \(p\) bằng trung vị của \(a\). Nhờ lời giải này, ta đưa bài toán gốc trở thành:
Cho một cây gồm \(n\) đỉnh, mỗi đỉnh có một giá trị \(a_i\). Với mỗi truy vấn \(u, v\) tìm giá trị trung vị \(p\), trên đường đi từ \(u\) tới \(v\).
Subtask \(2\) (\(15\%\) số điểm): \(x_i, y_i \leq 10\), \(u_i = i, v_i = i + 1\).
Tutorial
Khi các tọa độ nhỏ, ta có thể duyệt từng giá trị và kiểm tra liệu nó có phải trung vị hay không. Ở subtask này, cây có dạng đường thẳng nên ta có thể tạo mảng tiền tố \(s[i][j]\) là số lượng đỉnh có giá trị là \(i\) trên đoạn từ \(1\) tới \(j\) và sử dụng mảng này để tính số đỉnh có giá trị bất kỳ trên đường đi từ \(u\) tới \(v\).
Độ phức tạp: \(\mathcal{O}(n \times max(x_i, y_i) + q \times max(x_i, y_i)^2)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50005;
const int MAX_XY = 10;
int numNode, numQuery, x[MAX_N], y[MAX_N];
int cntX[MAX_N][MAX_XY + 1], cntY[MAX_N][MAX_XY + 1];
void initialize(int a[], int cnt[][MAX_XY + 1]) {
for (int i = 1; i <= numNode; ++i) {
for (int j = 1; j <= MAX_XY; ++j) {
cnt[i][j] = cnt[i - 1][j];
}
cnt[i][a[i]]++;
}
}
int findMedian(int left, int right, int cnt[][MAX_XY + 1]) {
int sum = 0;
for (int median = 1; median <= MAX_XY; ++median) {
sum += cnt[right][median] - cnt[left - 1][median];
if (sum >= (right - left + 2) / 2) {
return median;
}
}
assert(false);
}
int solveOne(int left, int right, int cnt[][MAX_XY + 1]) {
int res = 0, median = findMedian(left, right, cnt);
for (int i = 1; i <= MAX_XY; ++i) {
res += (cnt[right][i] - cnt[left - 1][i]) * abs(median - i);
}
return res;
}
int solve(int left, int right) {
return solveOne(left, right, cntX) + solveOne(left, right, cntY);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("MEETING.inp", "r", stdin);
freopen("MEETING.out", "w", stdout);
cin >> numNode >> numQuery;
for (int i = 1; i <= numNode; ++i) {
cin >> x[i];
}
for (int i = 1; i <= numNode; ++i) {
cin >> y[i];
}
for (int i = 1; i < numNode; ++i) {
int u, v;
cin >> u >> v;
assert(u == i && v == i + 1);
}
initialize(x, cntX);
initialize(y, cntY);
for (int i = 1; i <= numQuery; ++i) {
int left, right;
cin >> left >> right;
if (right < left) {
swap(left, right);
}
cout << solve(left, right) << "\n";
}
return 0;
}
Subtask \(3\) (\(25\%\) số điểm): \(u_i=i, v_i=i+1\).
Tutorial
Khi cây có dạng đường thẳng, bài toán trở thành: Tìm trung vị trên đoạn từ \(l\) tới \(r\) trên mảng 1 chiều. Trung vị của dãy chính là số lớn thứ \(\lceil \frac{(r - l + 1)}{2} \rceil\) trong đoạn. Để tìm số lớn thứ \(k\) bất kỳ trong đoạn \([l, r]\), ta sẽ áp dụng merge sort tree như sau:
Đầu tiên tạo mảng \(\text{id}[i]\) là vị trí của phần tử lớn thứ \(i\). Ví dụ mảng \(a = \{2, 1, 4, 5, 3\}\) sẽ cho mảng \(\text{id} = \{2, 1, 5, 3, 4\}\). Với mỗi truy vấn \(l, r, k\), ta sẽ cần tìm \(p\) nhỏ nhất sao cho \(\sum_{i = 1}^{p} [l \leq \text{id}[i] \leq r] \geq k\). Khi đó số lớn thứ \(p\) trong dãy \(a\) sẽ chính là số lớn \(k\) trong đoạn \([l,r]\) ta cần tìm.
Ta sẽ tạo merge sort tree với mảng \(\text{id}\). Để tìm \(p\) ta sẽ chặt nhị phân trên cây và sử dụng lower_bound và upper_bound để tìm số phần tử nằm trong khoảng \([l,r]\) trong một nút.
Độ phức tạp: \(\mathcal{O}(n \times \log_2(n) + q \times \log_2(n)^2)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50005;
struct FenwickTree {
int treeSize;
vector<long long> nodes;
void init(int treeSize) {
this->treeSize = treeSize;
nodes.assign(treeSize + 1, 0);
}
void update(int id, long long val) {
for (; id <= treeSize; id += (id & -id)) {
nodes[id] += val;
}
}
long long get(int id) {
long long result = 0;
for (; id >= 1; id -= (id & -id)) {
result += nodes[id];
}
return result;
}
long long get(long long left, long long right) {
return get(right) - get(left - 1);
}
};
struct SegmentTree {
private:
int treeSize;
vector<vector<int>> nodes;
void initTree(int id, int low, int high) {
nodes[id].clear();
if (low == high) {
return;
}
int mid = (low + high) / 2;
initTree(id * 2, low, mid);
initTree(id * 2 + 1, mid + 1, high);
}
void sortNode(int id, int low, int high) {
sort(nodes[id].begin(), nodes[id].end());
if (low == high) {
return;
}
int mid = (low + high) / 2;
sortNode(id * 2, low, mid);
sortNode(id * 2 + 1, mid + 1, high);
}
void update(int id, int low, int high, int pos, int val) {
nodes[id].push_back(val);
if (low == high) {
return;
}
int mid = (low + high) / 2;
if (pos <= mid) {
update(id * 2, low, mid, pos, val);
} else {
update(id * 2 + 1, mid + 1, high, pos, val);
}
}
int count(vector<int> &v, int left, int right) {
return upper_bound(v.begin(), v.end(), right) - lower_bound(v.begin(), v.end(), left);
}
int get(int id, int low, int high, int left, int right, int val) {
if (low == high) {
return low;
}
int cnt = count(nodes[id * 2], left, right);
int mid = (low + high) / 2;
if (cnt < val) {
return get(id * 2 + 1, mid + 1, high, left, right, val - cnt);
} else {
return get(id * 2, low, mid, left, right, val);
}
}
public:
void init(int treeSize) {
this->treeSize = treeSize;
int tmp = 1;
while (tmp < treeSize) {
tmp *= 2;
}
nodes.resize(tmp * 2);
initTree(1, 1, treeSize);
}
void update(int pos, int val) {
update(1, 1, treeSize, pos, val);
}
void sortNode() {
sortNode(1, 1, treeSize);
}
int get(int left, int right, int val) {
return get(1, 1, treeSize, left, right, val);
}
};
int numNode, numQuery;
int id[MAX_N], x[MAX_N], y[MAX_N], l[MAX_N], r[MAX_N];
long long answer[MAX_N], s[MAX_N];
vector<int> qr[MAX_N];
FenwickTree fenwickTree;
SegmentTree segmentTree;
void solve(int x[]) {
for (int i = 1; i <= numNode; i++) {
s[i] = s[i - 1] + x[i];
}
vector<pair<int, int>> v;
for (int i = 1; i <= numNode; i++) {
v.push_back({x[i], i});
}
sort(v.begin(), v.end());
for (int i = 0; i < numNode; i++) {
auto [val, ind] = v[i];
id[i + 1] = ind;
}
fenwickTree.init(numNode);
segmentTree.init(numNode);
for (int i = 1; i <= numNode; i++) {
segmentTree.update(i, id[i]);
}
segmentTree.sortNode();
for (int i = 1; i <= numNode; i++) {
qr[i].clear();
}
for (int i = 1; i <= numQuery; i++) {
int p = id[segmentTree.get(l[i], r[i], (r[i] - l[i] + 2) >> 1)];
qr[p].push_back(i);
}
for (auto [val, pos] : v) {
fenwickTree.update(pos, val);
for (int ind : qr[pos]) {
int cnt = r[ind] - l[ind] + 1;
int mid = (cnt + 1) >> 1;
long long tot = fenwickTree.get(l[ind], r[ind]);
answer[ind] += (long long)mid * val - fenwickTree.get(l[ind], r[ind]);
answer[ind] += (s[r[ind]] - s[l[ind] - 1] - tot) - (long long)(cnt - mid) * val;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("MEETING.inp", "r", stdin);
freopen("MEETING.out", "w", stdout);
cin >> numNode >> numQuery;
for (int i = 1; i <= numNode; i++) {
cin >> x[i];
}
for (int i = 1; i <= numNode; i++) {
cin >> y[i];
}
for (int i = 1; i < numNode; i++) {
int u, v;
cin >> u >> v;
assert(u == i && v == i + 1);
}
for (int i = 1; i <= numQuery; i++) {
cin >> l[i] >> r[i];
if (l[i] > r[i]) {
swap(l[i], r[i]);
}
}
solve(x);
solve(y);
for (int i = 1; i <= numQuery; i++) {
cout << answer[i] << "\n";
}
return 0;
}
Subtask \(4\) (\(20\%\) số điểm): \(x_i, y_i \leq 10\).
Tutorial
Tương tự subtask 2, với \(x_i,y_i\) nhỏ, ta có thể duyệt qua tất cả các giá trị và kiểm tra liệu giá trị đó có phải trung vị hay không. Khác với subtask 2, thay vì chỉ truy vấn lấy tổng trên một đoạn \([l,r]\) mà ta cần lấy tổng trên đường đi từ \(u\) tới \(v\).
ĐPT: \(O(max(x_i, y_i) \times (n + q) \times \log_2(n))\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50005;
const int MAX_XY = 10;
const int LOG = 15;
int numNode, numQuery;
int x[MAX_N], y[MAX_N];
int cntX[MAX_N][MAX_XY + 1], cntY[MAX_N][MAX_XY + 1];
int parent[MAX_N][LOG + 1], depth[MAX_N];
vector<int> adj[MAX_N];
void dfs(int node) {
cntX[node][x[node]]++;
cntY[node][y[node]]++;
for (int level = 1; level <= LOG; level++) {
parent[node][level] = parent[parent[node][level - 1]][level - 1];
}
for (int u : adj[node]) {
if (u != parent[node][0]) {
parent[u][0] = node;
for (int i = 1; i <= MAX_XY; i++) {
cntX[u][i] = cntX[node][i];
cntY[u][i] = cntY[node][i];
}
depth[u] = depth[node] + 1;
dfs(u);
}
}
}
int lca(int u, int v) {
if (depth[v] > depth[u]) {
swap(u, v);
}
for (int level = LOG; level >= 0; level--) {
if (depth[u] - (1LL << level) >= depth[v]) {
u = parent[u][level];
}
}
if (u == v) {
return u;
}
for (int level = LOG; level >= 0; level--) {
if (parent[u][level] != parent[v][level]) {
u = parent[u][level];
v = parent[v][level];
}
}
return parent[u][0];
}
int getSum(int u, int v, int val, int cnt[][MAX_XY + 1]) {
int p = lca(u, v);
return cnt[u][val] + cnt[v][val] - cnt[p][val] - cnt[parent[p][0]][val];
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
int findMedian(int u, int v, int cnt[][MAX_XY + 1]) {
int sum = 0;
for (int med = 1; med <= MAX_XY; ++med) {
sum += getSum(u, v, med, cnt);
if (sum >= (dist(u, v) + 2) / 2) {
return med;
}
}
assert(false);
}
int solveOne(int u, int v, int cnt[][MAX_XY + 1]) {
int res = 0, med = findMedian(u, v, cnt);
for (int i = 1; i < med; i++) {
res += getSum(u, v, i, cnt) * (med - i);
}
for (int i = med + 1; i <= MAX_XY; i++) {
res += getSum(u, v, i, cnt) * (i - med);
}
return res;
}
int solve(int u, int v) {
return solveOne(u, v, cntX) + solveOne(u, v, cntY);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("MEETING.inp", "r", stdin);
freopen("MEETING.out", "w", stdout);
cin >> numNode >> numQuery;
for (int i = 1; i <= numNode; i++) {
cin >> x[i];
}
for (int i = 1; i <= numNode; i++) {
cin >> y[i];
}
for (int i = 1; i < numNode; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
parent[1][0] = 0;
dfs(1);
for (int i = 1; i <= numQuery; i++) {
int u, v;
cin >> u >> v;
cout << solve(u, v) << "\n";
}
return 0;
}
Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Xét bài toán con sau đây: Với mỗi truy vấn \(u,v\), kiểm tra liệu trung vị của đường đi từ \(u\) tới \(v\) có không nhỏ hơn \(mid\) hay không. Để giải bài toán này, ta sẽ tính giá trị \(v[i]\) mới cho mỗi đỉnh như sau: nếu \(a[i] \geq k\) thì \(v[i] = 1\), ngược lại \(v[i] = -1\). Lúc này, trung vị của đường đi từ \(u\) tới \(v\) sẽ không nhỏ hơn \(mid \Leftrightarrow\) tổng \(v[i]\) với \(i\) thuộc đường đi từ \(u\) tới \(v\) lớn hơn \(0\).
Quay lại bài toán gốc, nếu ta giải được bài toán con nêu trên, ta chỉ cần chặt nhị phân để tìm \(mid\) nhỏ nhất không nhỏ hơn trung vị của đường đi \(u\rightarrow v\) và suy ra đó chính là trung vị cần tìm. Ta sẽ áp dụng kỹ thuật chặt nhị phân song song. Khi ta áp dụng kỹ thuật này, bài toán của chúng ta sẽ quy về xử lý 2 dạng truy vấn:
- Cập nhật giá trị của một đỉnh.
- Tìm tổng giá trị của các đỉnh thuộc đường đi \(u \rightarrow v\).
Để tìm tổng giá trị của đường đi \(u \rightarrow v\), ta sẽ cần một hàm \(get(u)\) tìm tổng từ \(1 \rightarrow u\). Gọi \(o=lca(u,v)\), \(par(u)\) là cha trực tiếp của \(u\), ta có tổng giá trị đường đi \(u \rightarrow v\) sẽ là \(get(u) + get(v) - get(o) - get(par(o))\).
Nhận xét rằng khi ta cập nhật giá trị của đỉnh \(u\), giá trị của hàm \(get(v)\) với \(v\) là tất cả các đỉnh thuộc cây con gốc \(u\) sẽ thay đổi. Do đó, bài toán quy về xử lý 2 dạng truy vấn:
- Cập nhật giá trị của cây con gốc \(u\).
- Lấy giá trị của một đỉnh.
Gọi \(\text{idDFS}[i]\) là thứ tự duyệt DFS của đỉnh \(i\) khi DFS từ \(1\), ta biết tập hợp \(\text{idDFS}[v]\) với \(v\) thuộc cây con gốc \(u\) sẽ là một dãy con liên tiếp từ \(\text{idDFS}[u]\) tới \(max(\text{idDFS}[v])\). Do đó 2 truy vấn trên sẽ chỉ đơn thuần là cập nhật giá trị của một đoạn liên tiếp và lấy giá trị một phần tử bất kỳ. Ta có thể sử dụng CTDL Fenwick Tree để xử lý.
Lưu ý: Đề yêu cầu in ra tổng khoảng cách chứ không chỉ là trung vị nên cần phải xử lý khoảng này nữa, phần này dành cho bạn đọc.
Độ phức tạp: \(\mathcal{O}((n + q)\times \log_2(n + q) \times log_2(n))\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50005;
const int LOG = 15;
struct Point {
int x, y;
};
struct Query {
int u, v;
Query(int _u = 0, int _v = 0) : u(_u), v(_v) {}
};
struct Quest {
int id, low, high;
Quest(int _id = 0, int _low = 0, int _high = 0) : id(_id), low(_low), high(_high) {}
};
struct FenwickTree {
int treeSize;
vector<long long> nodes;
void init(int treeSize) {
this->treeSize = treeSize;
nodes.assign(treeSize + 1, 0);
}
void update(int id, long long val) {
for (; id <= treeSize; id += (id & -id)) {
nodes[id] += val;
}
}
void update(int left, int right, int val) {
update(left, val);
update(right + 1, -val);
}
long long get(int id) {
long long result = 0;
for (; id >= 1; id -= (id & -id)) {
result += nodes[id];
}
return result;
}
};
int numNode, numQuery;
int a[MAX_N];
vector<int> adj[MAX_N];
Query query[MAX_N];
Point point[MAX_N];
int startTime[MAX_N], finishTime[MAX_N], depth[MAX_N], parent[MAX_N][LOG + 1], countTime = 0;
FenwickTree fenwickTree;
int val[MAX_N], real_val[MAX_N], median[MAX_N], idQuery[MAX_N];
long long res[MAX_N];
vector<int> pos[MAX_N];
void dfs(int node) {
startTime[node] = ++countTime;
for (int level = 1; level <= LOG; level++) {
parent[node][level] = parent[parent[node][level - 1]][level - 1];
}
for (int u : adj[node]) {
if (u != parent[node][0]) {
parent[u][0] = node;
depth[u] = depth[node] + 1;
dfs(u);
}
}
finishTime[node] = countTime;
}
int lca(int u, int v) {
if (depth[v] > depth[u]) {
swap(u, v);
}
for (int level = LOG; level >= 0; level--) {
if (depth[u] - (1LL << level) >= depth[v]) {
u = parent[u][level];
}
}
if (u == v) {
return u;
}
for (int level = LOG; level >= 0; level--) {
if (parent[u][level] != parent[v][level]) {
u = parent[u][level];
v = parent[v][level];
}
}
return parent[u][0];
}
void update(int id, int x) {
fenwickTree.update(startTime[id], finishTime[id], x);
a[id] += x;
}
void assign(int id, int x) {
fenwickTree.update(startTime[id], finishTime[id], -a[id]);
a[id] = x;
fenwickTree.update(startTime[id], finishTime[id], a[id]);
}
long long get(int u, int v) {
int o = lca(u, v);
return fenwickTree.get(startTime[u]) + fenwickTree.get(startTime[v]) - fenwickTree.get(startTime[o]) - (parent[o][0] ? fenwickTree.get(startTime[parent[o][0]]) : 0);
}
void compress() {
vector<int> b;
for (int i = 1; i <= numNode; i++) {
b.push_back(i);
}
sort(b.begin(), b.end(), [&](int x, int y) {
return val[x] < val[y];
});
for (int i = 1; i <= numNode; i++) {
real_val[i] = val[b[i - 1]];
}
for (int i = 1; i <= numNode; i++) {
val[b[i - 1]] = i;
}
}
void calculate() {
compress();
for (int i = 1; i <= numNode; i++) {
pos[i].clear();
}
for (int i = 1; i <= numNode; i++) {
pos[val[i]].push_back(i);
}
vector<Quest> currentQuest;
for (int i = 1; i <= numQuery; i++) {
currentQuest.push_back(Quest(i, 1, numNode));
}
while (!currentQuest.empty()) {
int current = 0;
fenwickTree.init(numNode);
vector<Quest> nextQuest, leftQuest, rightQuest;
for (int i = 1; i <= numNode; i++) {
a[i] = 0;
}
for (int i = 1; i <= numNode; i++) {
assign(i, 1);
}
for (int i = 0; i < (int)currentQuest.size(); i++) {
int id = currentQuest[i].id, u = query[id].u, v = query[id].v;
int low = currentQuest[i].low, high = currentQuest[i].high;
int mid = (low + high) >> 1;
if (mid > current) {
for (int j = 0; j < (int)leftQuest.size(); ++j) {
nextQuest.push_back(leftQuest[j]);
}
for (int j = 0; j < (int)rightQuest.size(); ++j) {
nextQuest.push_back(rightQuest[j]);
}
leftQuest.clear();
rightQuest.clear();
}
while (current < mid) {
for (int p : pos[current]) {
assign(p, -1);
}
current++;
}
if (get(u, v) <= 0) {
if (low < mid) {
leftQuest.push_back(Quest(id, low, mid - 1));
}
} else {
median[id] = mid;
if (mid < high) {
rightQuest.push_back(Quest(id, mid + 1, high));
}
}
}
for (int i = 0; i < (int)leftQuest.size(); i++) {
nextQuest.push_back(leftQuest[i]);
}
for (int i = 0; i < (int)rightQuest.size(); i++) {
nextQuest.push_back(rightQuest[i]);
}
leftQuest.clear();
rightQuest.clear();
currentQuest.clear();
for (int i = 0; i < (int)nextQuest.size(); i++) {
currentQuest.push_back(nextQuest[i]);
}
}
for (int i = 1; i <= numQuery; i++) {
idQuery[i] = i;
}
sort(idQuery + 1, idQuery + numQuery + 1, [&](int x, int y) {
return median[x] < median[y];
});
fenwickTree.init(numNode);
for (int i = 1; i <= numNode; i++) {
a[i] = 0;
}
int left = 1, pre = 1;
while (left <= numQuery) {
int right = left;
while (right <= numQuery && median[idQuery[right]] == median[idQuery[left]]) {
right++;
}
int current = median[idQuery[left]];
right--;
while (pre < current) {
for (int p : pos[pre]) {
update(p, real_val[pre]);
}
pre++;
}
for (int i = left; i <= right; i++) {
int id = idQuery[i];
int u = query[id].u, v = query[id].v;
int o = lca(u, v);
int num = depth[u] + depth[v] - 2 * depth[o] + 1;
res[id] += 1LL * (num - 1) / 2 * real_val[current] - get(u, v);
}
left = right + 1;
}
reverse(idQuery + 1, idQuery + numQuery + 1);
fenwickTree.init(numNode);
for (int i = 1; i <= numNode; i++) {
a[i] = 0;
}
left = 1, pre = numNode;
while (left <= numQuery) {
int right = left;
while (right <= numQuery && median[idQuery[right]] == median[idQuery[left]]) {
right++;
}
int current = median[idQuery[left]];
right--;
while (pre > current) {
for (int p : pos[pre]) {
update(p, real_val[pre]);
}
pre--;
}
for (int i = left; i <= right; i++) {
int id = idQuery[i];
int u = query[id].u, v = query[id].v;
int o = lca(u, v);
int num = depth[u] + depth[v] - 2 * depth[o] + 1;
res[id] += get(u, v) - 1LL * num / 2 * real_val[current];
}
left = right + 1;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("MEETING.inp", "r", stdin);
freopen("MEETING.out", "w", stdout);
cin >> numNode >> numQuery;
for (int i = 1; i <= numNode; i++) {
cin >> point[i].x;
}
for (int i = 1; i <= numNode; i++) {
cin >> point[i].y;
}
for (int i = 1; i < numNode; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= numQuery; i++) {
cin >> query[i].u >> query[i].v;
}
dfs(1);
for (int i = 1; i <= numNode; i++) {
val[i] = point[i].x;
}
calculate();
for (int i = 1; i <= numNode; i++) {
val[i] = point[i].y;
}
calculate();
for (int i = 1; i <= numQuery; i++) {
cout << res[i] << "\n";
}
return 0;
}
Bình luận