#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid(l,r) (l+r>>1)
#define lowbit(x) (x&-x)
#define sqrt sqrtl
using namespace std;
const int N=1e5+10,M=1+10,mod=1e9+7;
const double eps=1e-1;
const long double pi=acos(-1);
int n,m,q,a,b,c[N],cnt,head[N],fa[N],dep[N],siz[N],son[N],top[N],tot,lst[N],tr[4*N],tr2[N],ans[N];
struct qury{
  int l,r,id;
}quon[N];
struct edge{
  int nxt,to;
}edg[2*N];
struct node{
  int col,val;
};
vector<node>v[N];
void addedge(int x,int y){
  edg[++cnt].nxt=head[x];
  edg[cnt].to=y;
  head[x]=cnt;
}
void dfs1(int x,int f){
  fa[x]=f;
  dep[x]=dep[f]+1;
  siz[x]=1;
  for(int i=head[x];i;i=edg[i].nxt){
    int y=edg[i].to;
    if(y==f)continue;
    dfs1(y,x);
    siz[x]+=siz[y];
    if(!son[x]||siz[son[x]]<siz[y])son[x]=y;
  }
}
void dfs2(int x,int t){
  top[x]=t;
  if(!son[x]){
    lst[t]=x;
  }
  else{
    dfs2(son[x],t);
    for(int i=head[x];i;i=edg[i].nxt){
      int y=edg[i].to;
      if(y==fa[x]||y==son[x])continue;
      dfs2(y,y);
    }
  }
}
int lca(int x,int y){
  if(!x||!y)return x+y;
  while(top[x]!=top[y]){
    if(dep[top[x]]<dep[top[y]])swap(x,y);
    x=fa[top[x]];
  }
  if(dep[x]>dep[y])swap(x,y);
  return x;
}
void pushup(int p){
  tr[p]=lca(tr[ls(p)],tr[rs(p)]);
}
void build(int l,int r,int p){
  if(l==r){
    tr[p]=c[l];
    return;
  }
  build(l,mid(l,r),ls(p));
  build(mid(l,r)+1,r,rs(p));
  pushup(p);
}
bool cmp(qury a,qury b){
  return a.l>b.l;
}
void update2(int x,int y){
  while(x<=m){
    tr2[x]+=y;
    x+=lowbit(x);
  }
}
void update(int x,int y){
  while(x){
    int pre=dep[top[x]]-1;
    node f;
    while(1){
      f=v[top[x]].back();
      if(dep[x]<=dep[f.val])break;
      v[top[x]].pop_back();
      if(f.col)update2(f.col,pre-dep[f.val]);
      pre=dep[f.val];
    }
    if(f.col)update2(f.col,pre-dep[x]);
    if(f.val==x)v[top[x]].pop_back();
    update2(y,dep[x]-dep[top[x]]+1);
    v[top[x]].push_back((node){y,x});
    x=fa[top[x]];
  }
}
int query2(int x){
  int ret=0;
  while(x){
    ret+=tr2[x];
    x-=lowbit(x);
  }
  return ret;
}
int query(int l,int r,int L,int R,int p){
  if(l>=L&&r<=R)return tr[p];
  if(R<=mid(l,r))return query(l,mid(l,r),L,R,ls(p));
  if(L>mid(l,r))return query(mid(l,r)+1,r,L,R,rs(p));
  return lca(query(l,mid(l,r),L,R,ls(p)),query(mid(l,r)+1,r,L,R,rs(p)));
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>m>>q;
  for(int i=1;i<n;i++){
    cin>>a>>b;
    addedge(a,b);
    addedge(b,a);
  }
  cout<<"1"<<endl;
  dfs1(1,0);
  dfs2(1,1);
  for(int i=1;i<=n;i++){
    if(top[i]==i)v[i].push_back((node){0,lst[i]});
  }
  for(int i=1;i<=m;i++)cin>>c[i];
  build(1,m,1);
  for(int i=1;i<=q;i++){
    cin>>quon[i].l>>quon[i].r;
    quon[i].id=i;
  }
  sort(quon+1,quon+q+1,cmp);
  int idx=1;
  for(int i=m;i>=1;i--){
    update(c[i],i);
    while(idx<=q&&quon[idx].l==i){
      ans[quon[idx].id]=query2(quon[idx].r)-dep[query(1,m,i,quon[i].r,1)]+1;
      idx++;
    }
  }
  for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
  return 0;
}

思路参考第二篇题解。 提交记录