虚人「无」
题目背景
一点也不美丽的不死鸟。
那双锐爪,沾染了无辜的鲜血。
题目描述
给定二元序列 $\{(v_i,c_i)\}$ 和一棵以 $1$ 为根的有根树。第 $i$ 个点的点权是 $(v_i,c_i)$。
- 定义一个非根节点的权值为其子树内的 $c$ 的积乘上其子树补的 $v$ 的积。
- 定义一个根节点的权值为其子树内的 $c$ 的积。
形式化的讲,若 $u$ 不为根节点,则 $u$ 的权值 $f_u$ 为:
$$f_u=\prod\limits_{v\in \operatorname{substree}(u)} c_v\times \prod\limits_{v\notin \operatorname{substree}(u)} v_v$$
否则,其权值 $f_u$ 为:
$$f_u=\prod\limits_{v=1}^n c_v$$
试求整棵树所有节点的权值之和,答案对 $m$ 取模。请注意:保证 $m$ 是质数。
输入格式
第一行两个正整数 $n,m$。
接下来 $n-1$ 行,每行两个数 $u,v$,表示 $u,v$ 之间有一条边。
接下来一行 $n$ 个数,表示 $c_{1, 2, \dots, n}$。
接下来一行 $n$ 个数,表示 $v_{1, 2, \dots, n}$。
输出格式
输出一个数,表示答案对 $m$ 取模后的结果。
样例 #1
样例输入 #1
3 998244853
1 2
1 3
2 1 2
1 2 2
样例输出 #1
10
样例 #2
样例输入 #2
5 998244353
1 2
1 3
1 4
4 5
5 5 5 2 3
6 6 1 5 3
样例输出 #2
4656
提示
样例解释
(图片有误,应该交换 $v,c$ 的权值。)
数据范围及约定
对于 $100\%$ 的数据,满足 $1\le n\leq 3\times 10^5$,$1\leq v_i,c_i,m\leq 10^9$。
DFS序 + 前缀和
需要求得每个节点的所有 $c$ 的乘积,以及除了当前节点的子树的其他节点的 $v$ 的乘积,可以用 $dfs$ 序,求得 $dfs$ 序后可以知道任意节点的子树的范围,若节点为 $u$,子树大小为 $sz[u]$,则在 $dfs$ 序中的子树范围是 $[x,x + sz[u] - 1]$,$x$ 为点 $u$ 在 $dfs$ 序中开始的位置,详细见代码。
C++代码:
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10, M = N * 2;
int c[N], v[N];
LL f[N]; // 子树 c的乘积
int sz[N]; // 子树的大小
LL s1[N], s2[N]; // s1:v的前缀积 s2:v的后缀积
vector<int> g[N];
vector<int> b;
unordered_map<int, int> ma;
int n;
LL m;
void dfs(int u, int fa) {
f[u] = c[u];
sz[u] = 1;
for (int x : g[u]) {
if (x == fa) continue;
b.push_back(x);
dfs(x, u);
sz[u] += sz[x];
f[u] = (f[u] * f[x]) % m;
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n - 1; i ++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= n; i ++) sort(g[i].begin(), g[i].end());
LL s = 1;
for (int i = 1; i <= n; i ++) cin >> c[i];
for (int i = 1; i <= n; i ++) cin >> v[i];
b.push_back(0); // 使 b的下标从 1开始
b.push_back(1);
dfs(1, -1);
s1[0] = 1;
for (int i = 1; i <= n; i ++) s1[i] = s1[i - 1] * v[b[i]] % m; // 前缀积
s2[n + 1] = 1;
for (int i = n; i >= 1; i --) s2[i] = s2[i + 1] * v[b[i]] % m; // 后缀积
for (int i = 2; i <= n; i ++) ma[b[i]] = i; // 点 i在 dfs序中开始的位置
LL res = f[1];
for (int i = 2; i <= n; i ++) // 1为根
{
int x = ma[i]; // 点 i在 dfs序中开始的位置
int k = sz[i]; // 子树 i的大小
LL q = s1[x - 1], w = s2[x + k]; // 前缀积 * 后缀积 = 除了该子树的 v乘积
LL t = q * w % m;
res = (res + f[i] * t % m) % m;
}
cout << res;
return 0;
}
👍👍👍👍👍👍👍