#P3320. Seq

    ID: 2508 传统题 1000ms 512MiB 尝试: 112 已通过: 35 难度: 8 上传者: 标签>CF2400提高+/省选-贡献法点分治点分治容斥去重同向双指针稀疏状态重置

Seq

题目描述

给定一个有 NN 个点,N−1N-1 条边的无向连通图。

每个点都有黑白的属性,如果树上一条路径上黑色点个数和白色点个数一样多。称其为 GOOD 路径。易知两点间只有一条路径,那么给定点 AA 和点 BB 就能确定一条路径了。

现给点集 SS,定义其 GOOD 值为以点集中的点两两确定的路径中 GOOD 路径的个数。

现再给定一个序列,在一个方案中,某人可以选定其中一个连续子序列作为他的点集,另一个人取走剩下的点。现在某人想知道他的 GOOD 值比另一个人的 GOOD 值大的方案数。

输入格式

第一个一个整数 NN,表示点的个数。

接下来一行 NN 个数,描述每个点的着色,黑色为 11,白色为 00。

接下来 N−1N-1 行,每行两个数 a,ba,b,表示一条连接 a,ba,b 的边。

再接下来 NN 个数,为 1∼N1\sim N 的排列,描述给定的序列。

输出格式

一个整数,表示答案。

1
0
1
0

数据规模与约定

对于 100%100\% 的数据,1≤N≤1051\leq N\leq 10^5。