#BZOJ3772

BZOJ3772 精神污染 主席树 dfs序

  给出一个树,共n个节点。  有m条互不相同的树上路径。  现在让你随机选择2条路径,问两条路径存在包含关系的概率(输出最简分数)。  n,m<=100000  首先,暴力肯定过不去的。  然后,我们发现总选择的方案数是C(m,2)  然后重点是统计包含关系的。  现在,我们有一个做法。  我们先把整个树的df...