Link: Luogu https://www.luogu.com.cn/problem/P5298 or LibreOJ https://loj.ac/problem/2537
Solution
这个要查询的东西看起来没有什么意义啊、、
先看一下数据范围，应该是要 (O(nlog n)) 时间的。
本题的树高并非 (O(log n)) 不过其实对复杂度没什么影响、
题目保证了每个结点的子结点数不超过 2 。那么稍微思考一下马上就可以发现
这是不是可以直接模拟啊？后序遍历一下？
考虑对于某个结点维护它的值为多少多少的概率，一路从下往上合并？
那么很明显在转移的时候需要分别对左边和右边的每个值
乘上另一边转移过来的概率，再乘上一个另一边转移之前的概率和（是个前/后缀和）
不妨设结点 (i) 值为 (j) 的概率为 (p_{i,j})，那么应当这样转移：（记左右子树为 (l,r) 且离散化后最大权值为 (v)）
[p_{i,j}=p_{l,j}left[(1-p_x)sumlimits_{s=1}^{j-1}p_{r,s}+p_xsumlimits_{s=j+1}^{v}p_{r,s}
ight]+p_{r,j}left[(1-p_x)sumlimits_{s=1}^{j-1}p_{l,s}+p_xsumlimits_{s=j+1}^{v}p_{l,s}
ight]
]
？怎么做这个
看起来很复杂。
其实非常简单啊，等号左边跟等号右边完全独立。
那随便写写就可以了，，lazytag用来带好多好多的plj prj
然后sum是向叶子递归的时候一路带下去的，
就是普通权值线段树那种算前后缀和。
顺便记得逆元。
日常制杖time：①今天我写权值线段树没有排序就上了
②并且在用到之前把两个变量递归下去给改飞了（有两个递归应该大概没问题吧
③最后统计结果没有Pushdown
Code
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN = 3e5 + 10;
const int SEGN = MAXN << 5;
const int MOD = 998244353;
int n, SurLc[MAXN], SurRc[MAXN];
int val[MAXN], FormVal[MAXN];
int valtot = 0;
int Root[MAXN];
int SegLc[SEGN], SegRc[SEGN], SegTot = 0;
long long seg_mul_tag[SEGN], seg_prb_value[SEGN];
long long qpowm(long long a, long long b)
{
long long Ans = 1;
while (b)
{
if (b & 1)
{
Ans = Ans * a % MOD;
}
a = a * a % MOD;
b >>= 1;
}
return Ans;
}
void Insert(int &Pos, int L, int R, int Value)
{
Pos = ++SegTot;
seg_prb_value[Pos] = seg_mul_tag[Pos] = 1;
if (L < R)
{
int Mid = L + R >> 1;
if (Value <= Mid) Insert(SegLc[Pos], L, Mid, Value);
else Insert(SegRc[Pos], Mid + 1, R, Value);
}
}
void update(int pos, long long mul)
{
if (!pos) return;
seg_mul_tag[pos] = seg_mul_tag[pos] * mul % MOD;
seg_prb_value[pos] = seg_prb_value[pos] * mul % MOD;
return;
}
void pushdown(int pos)
{
if (!pos || seg_mul_tag[pos]==1) return;
if (SegLc[pos]) update(SegLc[pos], seg_mul_tag[pos]);
if (SegRc[pos]) update(SegRc[pos], seg_mul_tag[pos]);
seg_mul_tag[pos] = 1;
}
int MMmerge(int x, int y, long long xSum, long long ySum, long long pr)
{
if (!x && !y) return 0;
if (!x)
{
update(y, xSum);
return y;
}
if (!y)
{
update(x, ySum);
return x;
}
pushdown(x);
pushdown(y);
long long Temptemp = seg_prb_value[SegLc[x]], Temptemptemp = seg_prb_value[SegLc[y]];
long long orz = seg_prb_value[SegRc[x]], orzorz = seg_prb_value[SegRc[y]];
SegLc[x] = MMmerge(SegLc[x], SegLc[y], ((1ll-pr+MOD)%MOD*orz%MOD+xSum)%MOD, ((1ll-pr+MOD)%MOD*orzorz%MOD+ySum)%MOD, pr);
SegRc[x] = MMmerge(SegRc[x], SegRc[y], (1ll*pr*Temptemp%MOD+xSum) % MOD, (1ll*pr*Temptemptemp%MOD+ySum) % MOD, pr);
seg_prb_value[x] = (seg_prb_value[SegLc[x]] + seg_prb_value[SegRc[x]])%MOD;
return x;
}
void Initialize(int Position)
{
if (!SurLc[Position])
{
Insert(Root[Position], 1, valtot, val[Position]);
return;
}
if (SurRc[Position])
{
Initialize(SurLc[Position]);
Initialize(SurRc[Position]);
Root[Position] = MMmerge(Root[SurLc[Position]], Root[SurRc[Position]], 0, 0, val[Position]);
}
else
{
Initialize(SurLc[Position]);
Root[Position] = Root[SurLc[Position]];
}
}
long long Ans = 0;
void Calculate(int pos, int l, int r)
{
if (!pos) return;
if (l == r)
{
Ans = (Ans + 1ll * l * FormVal[l] % MOD * seg_prb_value[pos] % MOD * seg_prb_value[pos] % MOD) % MOD;
return;
}
pushdown(pos);
int mid = l + r >> 1;
Calculate(SegLc[pos], l, mid);
Calculate(SegRc[pos], mid + 1, r);
}
int main()
{
cin >> n;
for (int fa, i = 1; i <= n; ++i)
{
cin >> fa;
if (i==1) continue;
if (!SurLc[fa]) SurLc[fa] = i;
else SurRc[fa] = i;
}
for (int i = 1; i <= n; ++i)
{
cin >> val[i];
if (!SurLc[i])
{
FormVal[++valtot] = val[i];
}
else
{
val[i] = 1ll * val[i] * qpowm(10000, MOD - 2) % MOD;
}
}
sort(FormVal + 1, FormVal + 1 + valtot);
valtot = unique(FormVal + 1, FormVal + 1 + valtot) - FormVal - 1;
for (int i = 1; i <= n; ++i)
{
if (!SurLc[i])
{
val[i] = lower_bound(FormVal + 1, FormVal + 1 + valtot, val[i]) - FormVal;
}
}
Initialize(1);
Calculate(Root[1], 1, valtot);
cout << Ans;
return 0;
}