#include #include #include #include #include using namespace std; long long readInt(long long l,long long r,char endd){ long long x=0; int cnt=0; int fi=-1; bool is_neg=false; while(true){ char g=getchar(); if(g=='-'){ assert(fi==-1); is_neg=true; continue; } if('0'<=g && g<='9'){ x*=10; x+=g-'0'; if(cnt==0){ fi=g-'0'; } cnt++; assert(fi!=0 || cnt==1); assert(fi!=0 || is_neg==false); assert(!(cnt>19 || ( cnt==19 && fi>1) )); } else if(g==endd){ assert(cnt>0); if(is_neg){ x= -x; } if(!(l<=x && x<=r)){ cerr< adj[100100]; int sm_n=0; int sm_k=0; int sm_l=0; bool isTree[100100]; void dfs_istree(int nd){ isTree[nd]=true; for(int i=0;i lvl[b]){ swap(a,b); } b=kth(b,lvl[b]-lvl[a]); if(a==b)return a; for(int i=19;i>=0;i--){ if(dp[i][a] != dp[i][b]){ a=dp[i][a]; b=dp[i][b]; } } return dp[0][a]; } int move(int a,int b,int k){ int lc=lca(a,b); if(lvl[a] -lvl[lc] >= k){ return kth(a,k); } else { k -= lvl[a] -lvl[lc]; return kth(b,lvl[b]-lvl[lc] - k); } } int dist(int a,int b){ int lc=lca(a,b); return lvl[a] + lvl[b] - 2*lvl[lc]; } bool isOnPath(int a,int b,int c){ return dist(a,b) == dist(a,c) + dist(c,b); } int get_first(int a,int b,int c){ int lc= lca(a,b); if(kth(c,lvl[c]-lvl[lc]) == lc){ int g=lca(a,c); if(g == lc){ return lca(b,c); } else { return g; } } else { return lc; } } int A[100100],cur_a; int B[100100],cur_b; int nA[200200]; int nB[200200],m; int main(){ //freopen("02.txt","r",stdin); //freopen("02o.txt","w",stdout); T=readIntLn(1,1000); while(T--){ cur_a=cur_b=2; n=readIntSp(2,100000); k=readIntSp(2,100000); l=readIntLn(2,100000); sm_n += n; sm_k += n; sm_l += n; assert(sm_n <= 500000); assert(sm_k <= 500000); assert(sm_l <= 500000); for(int i=1;i<=n;i++){ adj[i].clear(); isTree[i]=false; } for(int i=2;i<=n;i++){ int u,v; u=readIntSp(1,n); v=readIntLn(1,n); adj[u].push_back(v); adj[v].push_back(u); } dfs_istree(1); for(int i=1;i<=n;i++){ assert(isTree[i]); } dfs_init(1,1,1); for(int i=1;i<20;i++){ for(int j=1;j<=n;j++){ dp[i][j] = dp[i-1][dp[i-1][j]]; } } for(int i=1;i<=k;i++){ if(i==k){ A[i]=readIntLn(1,n); } else { A[i]=readIntSp(1,n); } if(i>1){ assert(A[i] != A[i-1]); } } for(int i=1;i<=l;i++){ if(i==l){ B[i]=readIntLn(1,n); } else { B[i]=readIntSp(1,n); } if(i>1){ assert(B[i] != B[i-1]); } } m=1; nA[1]=A[1]; nB[1]=B[1]; while(cur_a<=k && cur_b<=l){ int dist_a = dist(nA[m],A[cur_a]); int dist_b = dist(nB[m],B[cur_b]); if(dist_a == dist_b){ m++; nA[m] = A[cur_a]; cur_a++; nB[m] = B[cur_b]; cur_b++; } else if(dist_a < dist_b){ m++; nA[m] = A[cur_a]; cur_a++; nB[m] = move(nB[m-1],B[cur_b],dist_a); } else { m++; nB[m] = B[cur_b]; cur_b++; nA[m] = move(nA[m-1],A[cur_a],dist_b); } } long long sol = 0; for(int i=1;i<=m-1;i++){ int st= get_first(nA[i],nA[i+1],nB[i]); int en= get_first(nA[i],nA[i+1],nB[i+1]); if(!isOnPath(nB[i],nB[i+1],st))continue; if(!isOnPath(nB[i],nB[i+1],en))continue; if(dist(nA[i],st) <= dist(nA[i],en)){ if(dist(nA[i],st) != dist(nB[i],st))continue; sol += dist(st,en) + 1; } else { int d1=dist(nB[i],st); int d2=dist(nA[i],st); int d3=dist(nB[i],en); int d4=dist(nA[i],en); if(d1 > d2)continue; if(d3 < d4)continue; if(abs(d1-d2) % 2 == 0) sol ++ ; } } for(int i=2;i<=m-1;i++){ if(nA[i] == nB[i])sol--; } cout<