A
\(u\) 被自己删去的概率为 \(\dfrac 1{siz_u}\)，即 \(u\) 有 \(\dfrac 1{siz_u}\) 概率被选，答案为 \(\sum\limits_{i = 1}^{n}\dfrac 1{siz_u}\)。
B
安装一个软件包 \(u\) 即安装 \(0\) 到 \(u\) 路径上所有软件包。
卸载一个软件包 \(u\) 即卸载 \(u\) 子树所有软件包。
树剖维护即可。
C
图上加边删边，询问连通块大小乘积。
以时间为下标建立线段树，树上每个节点维护 vector 表示当前时刻存在的边。
中序遍历线段树，进入节点时加入当前节点的贡献，离开节点时删去当前节点贡献。
遍历到叶子节点时记录答案。
使用并查集按秩合并统计贡献。每个连通块维护块内的节点个数 \(\text{s}\)。对于每一次加边，只会影响一个 \(\text{f}\) 和一个 \(\text{s}\)，用栈记录每次加边所影响的值，删去时返回之前的状态。
void query(int p)
{
int res = ans, num = 0;
for(int i = 0; i < s[p].v.size(); ++ i)
{
int u = s[p].v[i].first, v = s[p].v[i].second;
int x = find(u), y = find(v); if(x == y) continue;
ans = ans * inv[siz[x]] % mod * inv[siz[y]] % mod;
if(siz[x] < siz[y]) swap(x, y); t[++top] = {x, siz[x], y, siz[y]};
f[y] = x; siz[x] += siz[y]; ans = ans * siz[x] % mod; ++ num;
}
if(s[p].l == s[p].r) A[s[p].l] = ans;
else query(ls), query(rs);
for(int i = 1; i <= num; ++ i)
{
int a = t[top].a, b = t[top].b, c = t[top].c, d = t[top].d;
siz[a] = b; siz[c] = d; f[c] = c; -- top;
}
ans = res;
}
D
对于双向边部分缩点，单向边部分为 DAG。进行拓扑排序，每次对于当前连通分量跑 dij 即可。