#P11528. [2024省队模拟]邻域数点

    ID: 10676 传统题 3000ms 512MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>CF2600数据结构线段树树形DP图论DFS数学

[2024省队模拟]邻域数点

题目背景

小 YY 不喜欢 toptreetoptree 。

题目描述

有一个 nn 个点的树 T(r)=(V,E)T(r)=(V,E),其中 VV 为 TT 的点集, EE 为 TT 的边集,点的编号依次为 1,2,3,4,……,n1,2,3,4,……,n,根节点为 RootRoot ,记 x x 节点的深度 D(x)D(x) 表示节点 xx 到 RootRoot 的唯一简单路径的边的条数。

对于一个非空点集 S⊆VS\subseteq V ,我们可以对 SS 进行 任意次数 如下操作,称为拓展:

  • 选择 x∈S,y∈Sx\in S,y\in S ,然后把 xx 到 yy 的唯一简单路径上的所有点加入 SS 。

如果对于某一个由拓展得到的 S′S',其无法再通过拓展得到别的点集,我们就称 S′S' 是最初的点集 SS 的 完备邻域,记作 N(S)=S′N(S)=S' ,可证明 N(S)N(S) 是存在且唯一的。

令 R(S)R(S) 代表所有 x∈N(S)x\in N(S) 的 xx 中,D(x)D(x) 最小的 xx 的编号。

现在给定一个排列 p1,p2……,pnp_1,p_2……,p_n,请你对于 Root=1→nRoot=1\to n,求出 :

$$\sum_{1\leq l\leq r\le n}R(\{p_l,p_{l+1}……p_{r-1},p_r\})$$

输入格式

第一行一个正整数 nn 。

接下来 n−1n-1 行,每行两个整数 x,yx,y,代表一条树上的边 (x,y)∈E(x,y)\in E 。

接下来一个长度为 nn 的排列代表 pnp_n 。

输出格式

一共 nn 个数,第 ii 个数代表 Root=iRoot=i 时的答案。

输入样例

5
1 3
5 1
4 3
4 2
1 3 4 5 2

输出样例

27
46
45
54
55

数据规模

  • 15%15\%,1≤n≤5001\leq n\leq 500

  • 另15%15\%,1≤n≤20001\leq n\leq 2000

  • 另20%20\%,1≤n≤90001\leq n\leq 9000

  • 另20%20\%,xi=i,yi=i+1x_i=i,y_i=i+1

  • 另20%20\% 1≤n≤1×1051\leq n\leq 1\times 10^5

100%100\% ,1≤n≤3×1051\leq n\leq 3\times 10^5 。

弹跳(jump)