首先是比较简单的那一个——

给一个链，上面一堆带颜色点，每次询问区间内不同颜色个数。

考虑把询问按右端点排序，从左往右扫这个链，每扫到一个颜色就把他到上一次出现此颜色的区间集体加1，用树状数组支持区间加单点查，查一个位置的含义是当左端点在这个位置时区间内不同颜色的个数。

这个是朴素的。

接下来上一点难度——

还是一个链，但是每个点有点权，给一些区间，每次查询一个区间内的区间的并里包含点的权值和。

这个比较棘手，但还是可以考虑把询问按右端点从小到大排序，从左到右扫那些区间，扫到一个区间，这个区间内的点就挨个给他们到他们上一次出现那一段时间的贡献加上自己的贡献，再集体打上当前的时间标记。

暴力肯定是不行的，但是可以用线段树辅助操作，考虑到每一次操作最多只会分裂出原来的两个区域，而且吞掉原来的断点以后那些端点就不会存在，他覆盖的区间会变成一个整块，所以在线段树上暴力去找区间覆盖同一个标记的先加，再最后对一个大区间覆盖新标记并减，这样干时间复杂度甚至均摊并不占主要部分，而是线段树加树状数组操作的O(log2n)O(log^2n)。

最后是正题——

树上区间并求和，当然给出的区间也都是一些两点之间的路径。

前面链的部分其实已经说完了，树链剖分一下就没了，这回是O(nlog3n)O(nlog^3n)的

原题在这里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ld long double 
#define gtc() getchar()
#define fp(i,l,r) for(int i=l;i<=r;i++)
#define fb(i,l,r) for(int i=l;i>=r;i--)
#define pil pair<int,long long>
#define pii pair<int,int>
template <class T>
inline void read(T &s){
    T neg=1,ch=gtc();s=0;
    while(!isdigit(ch)){if(ch=='-')neg=-1;ch=gtc();}
    while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch-'0');ch=gtc();}
    s=s*neg;
}
const ll N=100050;
ll n,m,q,dfn[N],dep[N],sz[N],son[N],a[N],top[N],tot,tag[N*10],t[N],pre[N],ans[N],f[N];
vector<int> e[N];
pii qr[N];
struct fqr{
    ll l,r,p;
    bool operator <(const fqr &x)const{
        return r<x.r;
    }
}qs[N];
void dfs(ll x,ll fa){
    f[x]=fa;
    dep[x]=dep[fa]+1;
    sz[x]=1;
    for(auto i:e[x]){
        if(i==fa)continue;
        dfs(i,x);
        sz[x]+=sz[i];
        if(sz[i]>sz[son[x]])son[x]=i;
    }
}
void dfs2(ll x,ll fa,ll tp){
    top[x]=tp;
    dfn[x]=++tot;
    if(son[x])dfs2(son[x],x,tp);
    for(auto i:e[x]){
        if(i==fa||i==son[x])continue;
        dfs2(i,x,i);
    }
}
ll lowbit(ll x){return x&(-x);}
void add(ll x,ll v){
    for(int i=x;i<=m;i+=lowbit(i))t[i]+=v;
}
ll query(ll x){
    ll res=0;
    for(int i=x;i;i-=lowbit(i))res+=t[i];
    return res;
}
void modify(ll x,ll l,ll r,ll tl,ll tr,ll v){
    if(l>=tl&&r<=tr){
        add(v+1,pre[l-1]-pre[r]);
        tag[x]=v;
        return;
    }
    ll nxt=x<<1,mid=(l+r)>>1;
    if(tag[x]!=-1){
        tag[nxt]=tag[x];
        tag[nxt+1]=tag[x];
        tag[x]=-1;
    }
    if(tl<=mid)modify(nxt,l,mid,tl,tr,v);
    if(tr>mid)modify(nxt+1,mid+1,r,tl,tr,v);
}
void del(ll x,ll l,ll r,ll tl,ll tr){
    if(l>=tl&&r<=tr&&tag[x]!=-1){
        add(tag[x]+1,pre[r]-pre[l-1]);
        return ;
    }
    ll nxt=x<<1,mid=(l+r)>>1;
    if(tag[x]!=-1){
        tag[nxt]=tag[x];
        tag[nxt+1]=tag[x];
        tag[x]=-1;
    }
    if(tl<=mid)del(nxt,l,mid,tl,tr);
    if(tr>mid)del(nxt+1,mid+1,r,tl,tr);
}
void upd(ll x){
    ll nx=qr[x].first,ny=qr[x].second;
    while(top[nx]!=top[ny]){
        if(dep[top[nx]]>dep[top[ny]])swap(nx,ny);
        del(1,1,n,dfn[top[ny]],dfn[ny]);
        modify(1,1,n,dfn[top[ny]],dfn[ny],x);
        ny=f[top[ny]];
    }
    del(1,1,n,min(dfn[nx],dfn[ny]),max(dfn[nx],dfn[ny]));
    modify(1,1,n,min(dfn[nx],dfn[ny]),max(dfn[nx],dfn[ny]),x);
}
int main(){
    freopen("star.in","r",stdin);
    freopen("star.out","w",stdout);
    read(n),read(m),read(q);
    fp(i,1,n)read(a[i]);
    fp(i,1,n-1){
        ll u,v;
        read(u),read(v);
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    fp(i,1,m)read(qr[i].first),read(qr[i].second);
    fp(i,1,q)read(qs[i].l),read(qs[i].r),qs[i].p=i;
    sort(qs+1,qs+1+q);
    dfs(1,0);
    dfs2(1,0,1);
    fp(i,1,n)pre[dfn[i]]+=a[i];
    fp(i,1,n)pre[i]+=pre[i-1];
    ll nr=0;
    fp(i,1,q){
        while(nr<qs[i].r)upd(++nr);
        ans[qs[i].p]=query(qs[i].l);
    }
    fp(i,1,q)printf("%lld\n",ans[i]);
    return 0;
}