题解思路

本题是树形动态规划（Tree DP）的应用，目标是统计树上所有连通块中，节点权值为奇数的结点数量之和。树的结构保证了任何连通块都是一个子树的“子集”。我们可以通过对每个子树进行动态规划来解决这个问题。

1. 定义状态

设 $C[u]$ 表示以节点 $u$ 为根的子树的连通块数量（包括节点 $u$ 自身以及所有包含该节点的连通块）。我们可以通过子树的组合来递归地计算这个值。

• $C[u]$ 的计算公式为：
  

题目内容

小红拿到一棵$n$个结点的树，第i个点的权值为$a_i$。 现在，你需要求解，对于全部的连通块，它们内部中结点权值为奇数的结点数量之和是多少。由于答案可能很大,请将答案对$(10^9+7)$取模后输出。

她定义对于树上的两个点，如果它们相连，则称他们位于同一个连通块里。特别地，一个单独的点也可以构成一个连通块。连通块的大小即为连通块中节点的数量。

输入描述

第一行一个整数$n(1≤n≤10^5)$，表示结点个数。

第二行$n$个整数，第$i$个数为$a_i (1≤a_i≤10^9)$,表示一次权值。

接下来$n-1$行，每行两个整数$u,v(1≤u,v≤n,u≠v)$，表示$u,v$ 之间存在一条无向边。

输出描述

一个整数，表示所有连通块内部中结点权值为奇数的结点数量之和，结果对$10^9+7$取模。

样例1

输入

4
1 2 3 1
1 2
1 3
2 4

输出

14

说明

在这个样例中，树的形状如下图所示。一共可以分割得到$10$个不同的连通块:

• {$3$}号点构成的连通块，包含一个权值为奇数的点;

• {$1$}号点构成的连通块，包含一个权值为奇数的点;

• {$2$}号点构成的连通块，包含零个权值为奇数的点;

• {$4$}号点构成的连通块，包含一个权值为奇数的点;

• {$1,3$}号点构成的连通块，包含两个权值为奇数的点;

• {$1,2$}号点构成的连通块，包含一个权值为奇数的点;

• {$2,4$}号点构成的连通块，包含一个权值为奇数的点;

• {$3,1,2$}号点构成的连通块，包含两个权值为奇数的点;

• {$1, 2,4$}号点构成的连通块，包含两个权值为奇数的点;

• {$3,1,2,4$}号点构成的连通块，包含三个权值为奇数的点;

  综上，答案为$1+1+0+1+2+1+1+2+2+3=14$。