当前位置：首页 > news >正文

打卡信奥刷题（3321）用C++实现信奥题 P9208 虚人「无」

news 2026/5/26 12:33:59

P9208 虚人「无」

题目背景

一点也不美丽的不死鸟。

那双锐爪，沾染了无辜的鲜血。

题目描述

给定二元序列{(vi,ci)}\{(v_i,c_i)\}{(vi,ci)}和一棵以111为根的有根树。第iii个点的点权是(vi,ci)(v_i,c_i)(vi,ci)。

定义一个非根节点的权值为其子树内的ccc的积乘上其子树补的vvv的积。
定义一个根节点的权值为其子树内的ccc的积。

形式化的讲，若uuu不为根节点，则uuu的权值fuf_ufu为：

fu=∏v∈substree⁡(u)cv×∏v∉substree⁡(u)vvf_u=\prod\limits_{v\in \operatorname{substree}(u)} c_v\times \prod\limits_{v\notin \operatorname{substree}(u)} v_vfu=v∈substree(u)∏cv×v∈/substree(u)∏vv

否则，其权值fuf_ufu为：

fu=∏v=1ncvf_u=\prod\limits_{v=1}^n c_vfu=v=1∏ncv

试求整棵树所有节点的权值之和，答案对mmm取模。请注意：保证m\bm mm是质数。

输入格式

第一行两个正整数n,mn,mn,m。

接下来n−1n-1n−1行，每行两个数u,vu,vu,v，表示u,vu,vu,v之间有一条边。

接下来一行nnn个数，表示c1,2,…,nc_{1, 2, \dots, n}c1,2,…,n。

接下来一行nnn个数，表示v1,2,…,nv_{1, 2, \dots, n}v1,2,…,n。

输出格式

输出一个数，表示答案对mmm取模后的结果。

输入输出样例 #1

输入 #1

3 998244853 1 2 1 3 2 1 2 1 2 2

输出 #1

输入输出样例 #2

输入 #2

5 998244353 1 2 1 3 1 4 4 5 5 5 5 2 3 6 6 1 5 3

输出 #2

说明/提示

样例解释

（图片有误，应该交换v,cv,cv,c的权值。）

数据范围及约定

对于100%100\%100%的数据，满足1≤n≤3×1051\le n\leq 3\times 10^51≤n≤3×105，1≤vi,ci,m≤1091\leq v_i,c_i,m\leq 10^91≤vi,ci,m≤109。

C++实现

#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=3e5+3;intn,m;ll c[N],v[N],L[N],R[N],id[N],tot,ans;ll sc[N],lv[N],rv[N];vector<int>e[N];voiddfs(intx,intf){sc[x]=c[x];L[x]=++tot,id[tot]=x;for(autoy:e[x]){if(y==f)continue;dfs(y,x);sc[x]=(sc[x]*sc[y])%m;}R[x]=tot;}intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//个人习惯，输入输出优化cin>>n>>m;for(inti=1;i<n;i++){intx,y;cin>>x>>y;e[x].push_back(y);e[y].push_back(x);}for(inti=1;i<=n;i++)cin>>c[i];for(inti=1;i<=n;i++)cin>>v[i];dfs(1,0);lv[0]=rv[n+1]=1;for(inti=1;i<=n;i++)lv[i]=(lv[i-1]*v[id[i]])%m;for(inti=n;i>0;i--)rv[i]=(rv[i+1]*v[id[i]])%m;ans=sc[1]%m;for(inti=2;i<=n;i++)ans=(((lv[L[i]-1]*rv[R[i]+1])%m*sc[i])%m+ans)%m;cout<<ans;return0;}