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_vfuv∈substree(u)∏cv×v∈/substree(u)∏vv否则其权值fuf_ufu为fu∏v1ncvf_u\prod\limits_{v1}^n c_vfuv1∏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输入 #13 998244853 1 2 1 3 2 1 2 1 2 2输出 #110输入输出样例 #2输入 #25 998244353 1 2 1 3 1 4 4 5 5 5 5 2 3 6 6 1 5 3输出 #24656说明/提示样例解释图片有误应该交换v,cv,cv,c的权值。数据范围及约定对于100%100\%100%的数据满足1≤n≤3×1051\le n\leq 3\times 10^51≤n≤3×1051≤vi,ci,m≤1091\leq v_i,c_i,m\leq 10^91≤vi,ci,m≤109。C实现#includebits/stdc.husingnamespacestd;#definelllonglongconstintN3e53;intn,m;ll c[N],v[N],L[N],R[N],id[N],tot,ans;ll sc[N],lv[N],rv[N];vectorinte[N];voiddfs(intx,intf){sc[x]c[x];L[x]tot,id[tot]x;for(autoy:e[x]){if(yf)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);//个人习惯输入输出优化cinnm;for(inti1;in;i){intx,y;cinxy;e[x].push_back(y);e[y].push_back(x);}for(inti1;in;i)cinc[i];for(inti1;in;i)cinv[i];dfs(1,0);lv[0]rv[n1]1;for(inti1;in;i)lv[i](lv[i-1]*v[id[i]])%m;for(intin;i0;i--)rv[i](rv[i1]*v[id[i]])%m;anssc[1]%m;for(inti2;in;i)ans(((lv[L[i]-1]*rv[R[i]1])%m*sc[i])%mans)%m;coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
