#1107. Difficulty

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: lyyz001

题目描述

你是能看到 D(Difficulty) 题的 friends 呢~

——EXODUS

你现在有一棵二叉树,节点数为 n ,其中有 m 个为特殊节点,记为 S_1,S_2...S_m

一共有 Q 次询问,对于每次,你需要回答,给定节点 x 到达根节点路径上有没有特殊节点

初始根节点为 1 号节点

输入格式

第一行三个整数 n m Q ,含义如上所示

接下来 n-1 行每行两个整数 u\ ,\ v ,表示一条边

n+1 m 个整数,表示 S_1\ ,\ S_2\ ,\ ...\ , S_m

接下来 Q 行每行一个整数 x ,含义如上所示

输出格式

对于每次询问,如果不经过,输出 1 ,否则输出 0

样例

输入

7 2 3
1 2
1 3
2 4
2 5
3 6
3 7
2 3
2
1
3

输出

0
1
0

数据范围与提示

  1. 对于所有数据,满足 u 节点是 v 节点的父节点

  2. 对于所有数据,保证 S_i 互不相同

对于 70\% 的数据,满足 n,m,Q\leq 1000,S_i,x,u,v\leq n

对于 100\% 的数据,满足 n,m,Q\leq 4 \times 10^4,S_i,x,u,v\leq n