UOJ Logo Zijian Online Judge

ZOJ

#26. 简单数据结构题

Statistics

给一棵 $n$ 个点的树,点权开始为 $0$ ,有 $q$ 次操作,每次操作是选择一个点,把周围一圈点点权 $+1$(一个点周围的点为与该点距离为 $1$ 的点),在该操作后你需要输出当前周围一圈点点权的异或和。

由于输出量较大,设第 $i$ 个询问输出为 $ans_i$,你只需要输出

\begin{equation} [\sum^q_{i=1}ans_i \cdot (i^2+i)] \texttt{ mod } (10^9+7) \end{equation}

输入格式

第一行两个数 $n$ , $q$ ,表示树的点数和操作数。

接下来 $n-1$ 行每行两个数表示树上的一条边。

接下来 $q$ 行每行一个数 $x$,表示把 $x$ 周围一圈点点权 $+1$。

输出格式

输出一个 $[0,10^9+7)$ 的数,详见题目描述。

样例一

input

5 10
1 2
2 3
2 4
3 5
1
5
2
4
3
5
4
2
3
1

input

2060

explanation

加密前的输出如下:

1
1
2
2
2
3
4
4
7
6

样例二

见样例数据下载

样例三

见样例数据下载

样例四

见样例数据下载

限制与约定

对于 $80\texttt{%}$ 的数据,保证 $n = 1000$

对于 $90\texttt{%}$ 的数据,保证 $n = 100000$

对于 $100\texttt{%}$ 的数据,保证 $n = 500000$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

题目来源

钟子谦——IOI2018集训队自选题

下载

样例数据下载