妙妙 + 经典题。
难度：Hard。
题意
给定一棵 \(n\) 个结点的树，点有点权。树上有一些简单路径，编号分别为 \(1,2,\cdots,m\)。有 \(q\) 次询问，每次询问查询编号在 \([l,r]\) 中的路径的并的点权和。
题解
考虑一个经典题：定一个数列，每次询问一个区间不同元素的和。
这个问题是简单的，你只需要把询问离线下来，按右端点排序，每次拿树状数组维护最后面一个相同的元素即可（显然这是正确的）。
考虑树上问题怎么做，假设树的高度随机，则每个路径对应的不是一个点了，而是大约 \(\log\) 个点，但是操作还是一样的。
然后如果树的高度不随机，则考虑树剖。树剖出来的就是一个一个的 \(\texttt{dfn}\) 区间，则每个路径对应的就是不超过 \(\log\) 个区间。
那么考虑用 set 维护区间，然后每次加入新的区间就更新原来的区间。例如原有区间 \([3,6]\)，新加入区间 \([5,8]\)，则把 \([3,6]\) 变成 \([3,4]\)，同样树状数组维护，需要预处理一下前缀和。
时间复杂度好像是 \(\mathcal{O}(n\log^2n)\) 的，不过不太会证/ll，有没有会证的老哥私信一下/hanx。
好像还有一个分治做法，暂时还不会/dk。
代码
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define vi vector<int>
#define sz(a) ((int)(a.size()))
#define mset(f, x) memset(f, x, sizeof(f))
#define ALL(x) (x).begin(), (x).end()
#define rALL(x) (x).rbegin(), (x).rend()
#define uni(x) x.resize(unique(ALL(x)) - x.begin())
#define ull unsigned long long
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m, q;
ll a[N], sum[N], ans[N];
int head[N], nxt[M], to[M], cnt = 1;
int fa[N], dep[N], siz[N], son[N];
int dfn[N], top[N], tim = 0;
struct Path {int u, v;} paths[N];
struct Query {int l, r, id; bool operator < (const Query &p) const {return l < p.l;}} que[N];
void addEdge(int u, int v) {nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v;}
void dfs(int u, int p) {
dep[u] = dep[p] + 1; fa[u] = p;
siz[u] = 1; son[u] = -1;
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i]; if(v == p) continue;
dfs(v, u); siz[u] += siz[v];
if(son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
}
}
void redfs(int u, int t) {
dfn[u] = ++tim;
sum[tim] = sum[tim - 1] + a[u];
top[u] = t;
if(~son[u]) redfs(son[u], t);
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i]; if(v == fa[u] || v == son[u]) continue;
redfs(v, v);
}
}
namespace FenwickTree {
ll tree[N];
void init() {memset(tree, 0, sizeof(tree));}
void update(int x, ll v) {
while(x > 0) {tree[x] += v; x -= x & -x;}
}
ll query(int x) {
ll res = 0;
while(x <= m) {res += tree[x]; x += x & -x;}
return res;
}
};
set<Query> S;
void update_segment(int l, int r, int id) {
set<Query>::iterator it;
while((it = S.upper_bound((Query){r, 0, 0})) != S.begin()) {
if((--it) -> r < l) break;
Query v = *it; S.erase(it);
FenwickTree::update(v.id, sum[max(l, v.l) - 1] - sum[min(r, v.r)]);
if(v.l < l) S.insert((Query){v.l, l - 1, v.id});
if(v.r > r) S.insert((Query){r + 1, v.r, v.id});
}
FenwickTree::update(id, sum[r] - sum[l - 1]);
S.insert((Query){l, r, id});
}
void update_chain(int u, int v, int id) {
while(top[u] != top[v]) {
if(dfn[top[u]] < dfn[top[v]]) swap(u, v);
update_segment(dfn[top[u]], dfn[u], id);
u = fa[top[u]];
}
if(dfn[u] > dfn[v]) swap(u, v);
update_segment(dfn[u], dfn[v], id);
}
int main() {
freopen("star.in", "r", stdin); freopen("star.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
rep(i, 1, n) cin >> a[i];
rep(i, 1, n - 1) {
int u, v; cin >> u >> v;
addEdge(u, v); addEdge(v, u);
} dfs(1, 0); redfs(1, 1);
rep(i, 1, m) cin >> paths[i].u >> paths[i].v;
rep(i, 1, q) {
cin >> que[i].l >> que[i].r; que[i].id = i;
} sort(que + 1, que + q + 1, [](Query x, Query y) {return x.r < y.r;});
FenwickTree::init();
rep(i, 1, q) {
rep(j, que[i - 1].r + 1, que[i].r) update_chain(paths[j].u, paths[j].v, j);
ans[que[i].id] = FenwickTree::query(que[i].l);
}
rep(i, 1, q) cout << ans[i] << '\n';
return 0;
}