记一下。称 \(\forall j\in[l,r]\) 的 \(c_j\) 为关键点。
法一：
最好想的。
有个显然的结论，将所有关键点按 DFS 序排序，走过的边的数量为排序后相邻的点之间的距离。记走过的边的数量为 \(cnt_e\)，则此时这些关键点所构成的虚树的大小为 \(\frac{cnt_e}{2}+1\)。这时候可以直接暴力莫队，用 set 维护 DFS 序的前驱后继即可做到 \(n\sqrt{m}\log n\)。但这样是跑不过去的。发现只需要维护前驱后继，删除用链表可以做到 \(\mathcal{O}(1)\)，但不好执行加入操作。于是用一个只删不加的回滚莫队即可。
法二：
可以用 bitset 按 \(\log n\) 分块，类似于由乃救爷爷。但我不会 。
法三：
还有一种计算点集大小的方法，用数据结构维护一下，直接标记所有关键点走到某一个节点所经过的边，然后查询被标记的边的数量，这样配合回滚莫队也可以做到 \(\mathcal{O}(n\sqrt{m}\log^2n)\)。\(2\log\) 是因为用的是树链剖分。是不能通过的。
想一下为什么会这么麻烦。发现是因为必须要钦定某一个特定的点与其它点的路径标记。考虑能否将这个点固定下来。钦定这个点为 \(1\)，并让 \(1\) 作为根，看看会有什么变化。令 \(anc=\text{lca}\{c_j\}(j\in [l,r])\)，发现多出的答案就是 \(dep_{anc}-dep_1\)，其中 \(\text{lca}\{S\}\) 可以用 ST 表处理出。这样就可以不用回滚了。现在已经简单了不少，考虑如何去掉根号。
考虑离线后按 \(r\) 排序，以时间为值进行覆盖，则此时 \(anc\) 内值 \(\ge l\) 的边就一定会被统计。这时 \(anc\) 的子树外的边不会统计，但是这些边被被赋的值一定是当前最大的，直接减去即可。这是转化为了路径赋值 \((1,u)\)，全局查询值在某个区间的数的个数。
暴力的维护是简单的，直接上分块即可。
但这样的时间复杂度依然很高。想想区间赋值，可以直接用 ODT。这里 ODT 的复杂度显然是可以保证的，但是每次查询暴力扫一遍 \(1\sim m\) 的话会炸，再用一棵 BIT 维护值域即可。
有更优的实现方式：参考 Leasier 的思路，发现是对每条重链前缀赋值，可以使用 vector 替代 ODT。
时间复杂度：\(\mathcal{O}((n+q)\log^2n)\)，这里认为 \(n,m\) 同阶。
空间复杂度：\(\mathcal{O}(n\log n)\)
代码：
const int N=1e5+10;
int n,m,Q;
int a[N],st[18][N],log_2[N],ans[N];
struct BIT{
int v[N];
void add(int x,int y){assert(x);for(;x<=m;x+=x&-x)v[x]+=y;}
int ask(int x){
int res=0;
for(;x;x-=x&-x)res+=v[x];
return res;
}
} T;
int head[N],cnt_e=1;
struct edge{int v,nxt;} e[N<<1];
void adde(int u,int v){
e[++cnt_e]=(edge){v,head[u]};
head[u]=cnt_e;
}
int dfc,dfn[N],rdfn[N],sz[N],hv[N],d[N],fa[N],top[N];
void dfs1(int u,int fath){
sz[u]=1,d[u]=d[fath]+1,fa[u]=fath;
for(int i=head[u],v;i;i=e[i].nxt)if((v=e[i].v)!=fath){
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[hv[u]])hv[u]=v;
}
}
void dfs2(int u,int tp){
rdfn[dfn[u]=++dfc]=u,top[u]=tp;
if(!hv[u])return;
dfs2(hv[u],tp);
for(int i=head[u],v;i;i=e[i].nxt)if((v=e[i].v)!=hv[u]&&v!=fa[u])dfs2(v,v);
}
int glca(int u,int v){
while(top[u]!=top[v]){
if(d[top[u]]<d[top[v]])swap(u,v);
u=fa[top[u]];
}
if(d[u]<d[v])swap(u,v);
return v;
}
int qlca(int l,int r){
int k=log_2[r-l+1];
return glca(st[k][l],st[k][r-(1<<k)+1]);
}
vector<int> vec[N];pii q[N];
struct ODT{
int l,r;mutable int v;
ODT(const int &tl,const int &tr,const int &tv){l=tl;r=tr;v=tv;}
friend bool operator<(ODT a,ODT b){return a.l<b.l;}
};
set<ODT> odt;
typedef set<ODT>::iterator iter;
iter split(int x){
iter it=--odt.upper_bound((ODT){x,0,0});
if(it->l==x)return it;
assert(it!=odt.end());
int l=it->l,r=it->r,v=it->v;
odt.erase(it);
odt.insert((ODT){l,x-1,v});
return odt.insert((ODT){x,r,v}).first;
}
void assign(int l,int r,int tim){
iter itr=split(r+1),itl=split(l);
for(iter it=itl;it!=itr;it++)T.add(m-it->v+1,-(it->r-it->l+1));
odt.erase(itl,itr);
odt.insert((ODT){l,r,tim});
T.add(m-tim+1,r-l+1);
}
void upd(int u,int tim){
while(u){
assign(dfn[top[u]],dfn[u],tim);
u=fa[top[u]];
}
}
int main(){
scanf("%d%d%d",&n,&m,&Q);odt.insert((ODT){1,n,0});
for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
for(int i=1;i<=m;i++)scanf("%d",&a[i]),st[0][i]=a[i];
dfs1(1,0),dfs2(1,1);
for(int i=2;i<=m;i++)log_2[i]=log_2[i>>1]+1;
for(int i=1;i<=17;i++)for(int j=1;j+(1<<i)-1<=m;j++)st[i][j]=glca(st[i-1][j],st[i-1][j+(1<<i-1)]);
for(int i=1;i<=Q;i++)cin>>q[i].first>>q[i].second,vec[q[i].second].eb(i),ans[i]=-d[qlca(q[i].first,q[i].second)]+d[1];
for(int i=1;i<=m;i++){
upd(a[i],i);
for(int j:vec[i])ans[j]+=T.ask(m-q[j].first+1);
}
for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
return 0;
}