题意简述：\(n\)个节点的树，第\(i\)个节点有权值\(a_i\)，有\(m\)条路径，\(q\)次询问，每次询问编号在\([l, r]\)的路径的并的权值和。
先考虑树随机的部分分。将询问按照右端点排序，设\(f_{i, j}\)为右端点在\(i\)，左端点在\(j\)的答案，考虑\(i\)变为\(i+1\)时，\(j\)这一维的变化。
对于路径\(i\)覆盖的点\(k\)，假设它上一次被覆盖是在第\(u\)条路径。显然对于此后的任意询问，只要包含第\(u\)条路径，就必定包含第\(i\)条路径，则路径\(u\)对点\(k\)的覆盖已经没有用处。可以用树状数组维护\(j\)这一维，在第\(i\)条路径的位置增加\(a_k\)的权值，在第\(u\)条路径的位置减少\(a_k\)的权值。对于随机树，路径长度期望为\(\log n\)，总修改次数不超过\(n\log n\)次。
对于剩余情况，复杂度的瓶颈在于加入每条路径时需要修改\(O(n)\)个点。
发现每次修改的都是一条连续路径。如果树剖后在每条重链上一次性处理一整个同色连续段，则这条重链上的连续段可分为以下三类：
与待修改连续段无交集：不会对复杂度产生影响。
完全被待修改连续段覆盖：产生\(1\)次修改的代价，此后连续段个数\(-1\)，总修改次数不会超过连续段个数。
部分被待修改连续段覆盖：产生\(1\)次修改的代价，连续段个数增加\(O(1)\)个，但每次最多有\(2\)个此类连续段。
由于对于每条重链最多产生\(n\)个连续段，因此修改的次数是均摊\(O(1)\)的。
用\(\rm{set}\)维护每条重链的连续段，总复杂度\(O(n\log^2 n)\)。
#include <set>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#define R register
#define ll long long
using namespace std;
const int N = 110000, M = N << 1;
int n, m, q, a[N], hd[N], nxt[M], to[M], noedg = 1, size[N], son[N], fa[N], dep[N], rev[N], dfn[N], top[N], cnt;
ll ans[N], sum[N], tree[N];
struct path {
int x, y;
}p[N];
struct queries {
int lt, rt, ind;
queries(int l = 0, int r = 0, int i = 0) : lt(l), rt(r), ind(i) {}
inline bool operator < (const queries &x) const {
return rt < x.rt;
}
}que[N];
set<queries> col[N];
void addEdg(int x, int y) {
nxt[++noedg] = hd[x], hd[x] = noedg, to[noedg] = y;
nxt[++noedg] = hd[y], hd[y] = noedg, to[noedg] = x;
return;
}
template <class T> inline void read(T &x) {
x = 0;
char ch = getchar(), w = 0;
while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x = w ? -x : x;
return;
}
void dfs1(int now) {
dep[now] = dep[fa[now]] + 1, size[now] = 1;
for (R int i = hd[now], v; i; i = nxt[i]) {
if ((v = to[i]) == fa[now]) continue;
fa[v] = now, dfs1(v), size[now] += size[v];
son[now] = size[son[now]] > size[v] ? son[now] : v;
}
return;
}
void dfs2(int now) {
dfn[now] = ++cnt, rev[cnt] = now, sum[now] = sum[fa[now]] + a[now];
if (son[now]) top[son[now]] = top[now], dfs2(son[now]);
for (R int i = hd[now], v; i; i = nxt[i]) {
if ((v = to[i]) == fa[now] || v == son[now]) continue;
top[v] = v, dfs2(v);
}
return;
}
inline int getLca(int x, int y) {
while (top[x] != top[y])
dep[top[x]] <= dep[top[y]] ? (y = fa[top[y]]) : (x = fa[top[x]]);
return dep[x] <= dep[y] ? x : y;
}
inline int getSon(int x, int anc) {
if (top[x] == top[anc]) return son[anc];
x = top[x];
while (top[fa[x]] != top[anc]) x = top[fa[x]];
return fa[x] == anc ? x : son[anc];
}
inline void modify(int x, ll w) {
while (x <= m) tree[x] += w, x += x & -x;
return;
}
inline ll query(int x) {
ll ret = 0;
while (x) ret += tree[x], x -= x & -x;
return ret;
}
inline void modifyChain(int x, int anc, int ind) {
int flag = 1, y;
while (flag) {
if (top[x] == top[anc])
y = anc, flag = 0;
else
y = top[x];
auto it = col[top[x]].upper_bound(queries(0, dfn[x]));
if (it != col[top[x]].end() && it->lt <= dfn[x]) {
if (it->lt < dfn[y]) {
modify(it->ind, sum[fa[y]] - sum[x]);
queries tmp1(dfn[x] + 1, it->rt, it->ind), tmp2(it->lt, dfn[fa[y]], it->ind);
col[top[x]].erase(it), col[top[x]].insert(tmp1);
it = col[top[x]].insert(tmp2).first;
}
else {
modify(it->ind, sum[fa[rev[it->lt]]] - sum[x]);
queries tmp(dfn[x] + 1, it->rt, it->ind);
col[top[x]].erase(it);
it = col[top[x]].insert(tmp).first;
}
}
while (it != col[top[x]].begin() && (--it)->rt >= dfn[y]) {
if (it->lt >= dfn[y]) {
modify(it->ind, sum[fa[rev[it->lt]]] - sum[rev[it->rt]]);
it = col[top[x]].erase(it);
}
else {
modify(it->ind, sum[fa[y]] - sum[rev[it->rt]]);
queries tmp(it->lt, dfn[fa[y]], it->ind);
col[top[x]].erase(it);
it = col[top[x]].insert(tmp).first;
}
}
col[top[x]].insert(queries(dfn[y], dfn[x], ind)), x = fa[top[x]];
}
return;
}
int main() {
int x, y;
read(n), read(m), read(q);
for (R int i = 1; i <= n; ++i)
read(a[i]);
for (R int i = 1; i < n; ++i)
read(x), read(y), addEdg(x, y);
for (R int i = 1; i <= m; ++i)
read(p[i].x), read(p[i].y);
for (R int i = 1; i <= q; ++i)
read(que[i].lt), read(que[i].rt), que[i].ind = i;
sort(que + 1, que + 1 + q);
dfs1(1), dfs2(1);
for (R int i = 1, tl = 0; i <= q; ++i) {
while (tl < que[i].rt) {
++tl, x = p[tl].x, y = p[tl].y;
int lca = getLca(p[tl].x, p[tl].y);
modify(tl, sum[x] + sum[y] - sum[lca] - sum[fa[lca]]);
if (dfn[x] > dfn[y]) swap(x, y);
modifyChain(y, lca, tl);
if (lca != x) {
int son = getSon(x, lca);
modifyChain(x, son, tl);
}
}
ans[que[i].ind] = query(que[i].rt) - query(que[i].lt - 1);
}
for (R int i = 1; i <= q; ++i)
printf("%lld\n", ans[i]);
return 0;
}