题目描述
题解
一种好想/好写/跑得比**记者还快的做法：
对所有询问排序，按照R递增的顺序来处理
维护每个点最后一次被覆盖的时间，显然当前右端点为R时的答案为所有时间≥L的点的权值之和
LCT随便覆盖一发，保证一段重链上的点的颜色相同（这样可以直接修改），用树状数组维护权值和
由于要保证颜色相同，所以不能随便moveroot
覆盖时先把x和y的lca和原树上的父亲断掉，把x-->lca这一段覆盖，然后再覆盖y-->lca向y方向的儿子
反正随便写应该就能过（
另一种做法
也就是题解的难想/难写/跑得没**记者快的做法
原以为跑得很快就去写了一发
把每个L<R的询问下放到线段树上的一个l≤L≤mid且mid+1≤R≤r的区间[l,r]上（显然这样的区间是唯一的）
由于询问必定经过mid，所以每个询问可以表示成左边的贡献+右边的贡献
为了不算重，考虑维护把每个点的贡献放到当前区间内最早覆盖该点的路径上，算答案就直接求和
对于每个有询问的区间，把路径l~r的有关点建虚树（分点和段），依次把mid+1~r的每条边在虚树上覆盖，每个点/段记录下最早被覆盖的时间，用并查集优化，同时求出加入每条边之后新增的贡献，树状数组维护
接着按L从大到小处理每个询问，计算每加入一条路径时计算覆盖的贡献
因为L递减，所以每条路径加入后就不会删除，同时为了防止算重，要把这条路径上的贡献在树状数组上的原位置减去
然而这样似乎跑不过（
优化：
①RMQ求LCA（欧拉序，xy的lca=x~y路径上深度最浅的点的父亲）
②对于每个区间，R的扫描范围=mid+1~max(区间中询问的R)
code
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define inc(x,y) (bg[x]<=bg[y] && ed[y]<=ed[x])
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define low(x) (x&-(x))
using namespace std;
struct type{
int x,y,id;
} q[100001];
int p[200001];
int P[18];
long long tr[100001];
int a[200001][2];
int b[200002];
int c[100001]; //final xushu
int ls[100001];
int A[100001][4];
int Ls[400001];
int w[100001];
int cl[100001];
int cr[100001];
int Lca[100001];
int bg[100001];
int ed[100001];
int Bg[100001];
int Ed[100001];
int fa[100001];
int D[100001];
int ql[100001];
int qr[100001];
int Fa[100001];
int Fa2[100001]; //beiyong
int d[100001];
long long ans[100001];
long long Sum[100001];
long long sum[100001]; //duan
long long num[100001]; //dian
long long Num[100001]; //duan
bool bz[100001]; //dian
bool Bz[100001]; //duan
int rmq[200001][18];
int B[200001]; //euler
int n,m,Q,i,j,k,l,len,Len,lenb,lenc,lenq,LEN,N,mr;
bool cmp(int a,int b)
{
return bg[a]<bg[b];
}
bool Cmp(type a,type b)
{
return a.x>b.x;
}
void New(int x,int y)
{
++len;
a[len][0]=y;
a[len][1]=ls[x];
ls[x]=len;
}
void NEW(int t,int x,int y,int id)
{
++Len;
A[Len][0]=x;
A[Len][1]=y;
A[Len][2]=id;
A[Len][3]=Ls[t];
Ls[t]=Len;
}
void swap(int &x,int &y)
{
int z=x;
x=y;
y=z;
}
void dfs(int Fa,int t)
{
int i;
B[++N]=t;
Bg[t]=N;
bg[t]=++j;
fa[t]=Fa;
D[t]=D[Fa]+1;
Sum[t]=Sum[Fa]+w[t];
for (i=ls[t]; i; i=a[i][1])
if (a[i][0]!=Fa)
dfs(t,a[i][0]);
B[++N]=t;
Ed[t]=N;
ed[t]=j;
}
int lca(int x,int y)
{
if (inc(x,y)) return x;
if (inc(y,x)) return y;
if (Bg[x]>Bg[y]) swap(x,y);
x=Bg[x],y=Ed[y];
int Len=y-x+1;
if (D[rmq[x][p[Len]]]<D[rmq[y-P[p[Len]]+1][p[Len]]])
return fa[rmq[x][p[Len]]];
else
return fa[rmq[y-P[p[Len]]+1][p[Len]]];
}
void change(int t,int l,int r,int x,int y,int id)
{
int mid=(l+r)/2;
if (x<=mid && mid+1<=y)
{
NEW(t,x,y,id);
return;
}
if (y<=mid)
change(t*2,l,mid,x,y,id);
else
change(t*2+1,mid+1,r,x,y,id);
}
void Change(int t,long long s)
{
while (t<=LEN)
{
tr[t]+=s;
t+=low(t);
}
}
void Clear(int t)
{
while (t<=LEN)
{
tr[t]=0;
t+=low(t);
}
}
long long Find(int t)
{
long long ans=0;
while (t)
{
ans+=tr[t];
t-=low(t);
}
return ans;
}
void build()
{
int i,j,k,l=0;
sort(b+1,b+lenb+1,cmp);
l=1;
d[1]=1;
fo(i,1,lenb)
if (b[i]!=d[l])
{
k=lca(b[i],d[l]);
while (!inc(d[l],k))
{
Fa2[d[l]]=d[l-1];
c[++lenc]=d[l];
--l;
}
if (d[l]!=k)
{
Fa2[d[l+1]]=k;
d[++l]=k;
}
d[++l]=b[i];
}
while (l)
{
Fa2[d[l]]=d[l-1];
c[++lenc]=d[l];
--l;
}
fo(i,1,lenc)
sum[c[i]]=Sum[c[i]]-Sum[Fa2[c[i]]]-w[c[i]];
}
void solve(int t,int L,int R)
{
int I,i,j,k,l,mid=(L+R)/2;
long long Ans=0,SUM;
LEN=R-L+1;
lenb=0;
lenc=0;
fo(i,L,R)
b[++lenb]=cl[i],b[++lenb]=cr[i];
build();
// right
fo(i,1,lenc)
num[c[i]]=0,Num[c[i]]=0,Fa[c[i]]=Fa2[c[i]];
fo(i,mid+1,mr)
{
SUM=0;
l=0;
j=cl[i];
while (!inc(j,Lca[i]))
{
d[++l]=j;
if (!num[j]) {num[j]=i;SUM+=w[j];}
if (!Num[j]) {Num[j]=i;SUM+=sum[j];}
j=Fa[j];
}
j=cr[i];
while (!inc(j,Lca[i]))
{
d[++l]=j;
if (!num[j]) {num[j]=i;SUM+=w[j];}
if (!Num[j]) {Num[j]=i;SUM+=sum[j];}
j=Fa[j];
}
if (!num[Lca[i]]) {num[Lca[i]]=i;SUM+=w[Lca[i]];}
fo(k,1,l)
Fa[d[k]]=Lca[i];
Change(i-L+1,SUM);
}
// left
fo(i,1,lenc)
Fa[c[i]]=Fa2[c[i]],bz[c[i]]=0,Bz[c[i]]=0;
q[0].x=mid+1;
fo(I,1,lenq)
{
fd(i,q[I-1].x-1,q[I].x)
{
SUM=0;
l=0;
j=cl[i];
while (!inc(j,Lca[i]))
{
d[++l]=j;
if (!bz[j]) {bz[j]=1;SUM+=w[j];}
if (!Bz[j]) {Bz[j]=1;SUM+=sum[j];}
if (num[j]) {Change(num[j]-L+1,-w[j]),num[j]=0;}
if (Num[j]) {Change(Num[j]-L+1,-sum[j]),Num[j]=0;}
j=Fa[j];
}
j=cr[i];
while (!inc(j,Lca[i]))
{
d[++l]=j;
if (!bz[j]) {bz[j]=1;SUM+=w[j];}
if (!Bz[j]) {Bz[j]=1;SUM+=sum[j];}
if (num[j]) {Change(num[j]-L+1,-w[j]),num[j]=0;}
if (Num[j]) {Change(Num[j]-L+1,-sum[j]),Num[j]=0;}
j=Fa[j];
}
if (!bz[Lca[i]]) {bz[Lca[i]]=1;SUM+=w[Lca[i]];}
if (num[Lca[i]]) {Change(num[Lca[i]]-L+1,-w[Lca[i]]),num[Lca[i]]=0;}
fo(k,1,l)
Fa[d[k]]=Lca[i];
Ans+=SUM;
}
ans[q[I].id]=Ans+Find(q[I].y-L+1);
}
// clear
memset(tr,0,(LEN+1)*8);
}
void work(int t,int l,int r)
{
int mid=(l+r)/2,i;
if (l==r) return;
if (Ls[t])
{
mr=l;
lenq=0;
for (i=Ls[t]; i; i=A[i][3])
{
++lenq;
q[lenq].x=A[i][0];
q[lenq].y=A[i][1];
q[lenq].id=A[i][2];
mr=max(mr,A[i][1]);
}
sort(q+1,q+lenq+1,Cmp);
solve(t,l,r);
}
work(t*2,l,mid);
work(t*2+1,mid+1,r);
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("b.out","w",stdout);
freopen("star.in","r",stdin);
freopen("star.out","w",stdout);
scanf("%d%d%d",&n,&m,&Q);
fo(i,1,n)
scanf("%d",&w[i]);
fo(i,2,n)
{
scanf("%d%d",&j,&k);
New(j,k);
New(k,j);
}
j=0;
dfs(0,1);
fo(i,1,N)
{
rmq[i][0]=B[i];
p[i]=floor(log(i)/log(2));
}
P[0]=1;
fo(i,1,17)
P[i]=P[i-1]<<1;
k=1;l=2;
fo(i,1,17)
{
fo(j,1,N-l+1)
if (D[rmq[j][i-1]]<D[rmq[j+k][i-1]])
rmq[j][i]=rmq[j][i-1];
else
rmq[j][i]=rmq[j+k][i-1];
k<<=1;l<<=1;
}
fo(i,1,m)
{
scanf("%d%d",&cl[i],&cr[i]);
Lca[i]=lca(cl[i],cr[i]);
}
fo(i,1,Q)
{
scanf("%d%d",&ql[i],&qr[i]);
if (ql[i]<qr[i])
change(1,1,m,ql[i],qr[i],i);
else
ans[i]=Sum[cl[ql[i]]]+Sum[cr[ql[i]]]-Sum[Lca[ql[i]]]-Sum[fa[Lca[ql[i]]]];
}
work(1,1,m);
fo(i,1,Q)
printf("%lld
",ans[i]);
fclose(stdin);
fclose(stdout);
return 0;
}