当前位置 博文首页 > Jozky86的博客：牛客练习赛55E树
牛客练习赛55E树
你有一颗大小为n 的树，点从 1 到 n 标号。
设dis(x,y)表示 x 到 y 的距离。
求
∑
i
=
1
n
∑
j
=
1
n
d
i
s
2
(
i
,
j
)
\sum_{i=1}^{n}\sum_{j=1}^{n}dis^2(i,j)
∑i=1n?∑j=1n?dis2(i,j)对998244353取模的结果
我们以1为根，设dep[i]表示第i个点的深度
d
i
s
(
x
,
y
)
=
d
e
p
[
x
]
+
d
e
p
[
y
]
?
2
d
e
p
[
l
c
a
(
x
,
y
)
]
dis(x,y)=dep[x]+dep[y]-2dep[lca(x,y)]
dis(x,y)=dep[x]+dep[y]?2dep[lca(x,y)]
所以
将dis(i,j)展开
d
i
s
2
(
i
,
j
)
=
d
e
p
2
[
x
]
+
d
e
p
2
[
y
]
+
2
?
d
e
p
[
x
]
?
d
e
p
[
y
]
+
4
?
d
e
p
2
[
l
c
a
(
x
,
y
)
]
?
4
?
(
d
e
p
[
x
]
+
d
e
p
[
y
]
)
?
d
e
p
[
l
c
a
(
x
,
y
)
]
dis^2(i,j)=dep^2[x]+dep^2[y]+2*dep[x]*dep[y]+4*dep^2[lca(x,y)]-4*(dep[x]+dep[y])*dep[lca(x,y)]
dis2(i,j)=dep2[x]+dep2[y]+2?dep[x]?dep[y]+4?dep2[lca(x,y)]?4?(dep[x]+dep[y])?dep[lca(x,y)]
对于前两项
d
e
p
2
[
x
]
+
d
e
p
2
[
y
]
dep^2[x]+dep^2[y]
dep2[x]+dep2[y]:因为x和y都是枚举1~n，所以就是求
2
d
e
p
[
i
]
?
d
e
p
[
i
]
,
1
<
=
i
<
=
n
2dep[i]*dep[i],1<=i<=n
2dep[i]?dep[i],1<=i<=n
对于第三项：
2
?
d
e
p
[
x
]
?
d
e
p
[
y
]
2*dep[x]*dep[y]
2?dep[x]?dep[y]:先求出
m
a
x
x
=
∑
i
=
1
n
d
e
p
[
i
]
maxx=\sum_{i=1}^{n}dep[i]
maxx=∑i=1n?dep[i]，然后用
∑
i
=
1
n
m
a
x
x
?
d
e
p
[
i
]
?
2
\sum_{i=1}^{n}maxx*dep[i]*2
∑i=1n?maxx?dep[i]?2
对于后两部分，我们需要计算lca(x,y)=i的(x,y)这样的数对个数，以及dep[x]+dep[y]之和
先解答第一个：数对个数为：
s
i
z
e
2
[
i
]
?
∑
j
∈
s
o
n
[
i
]
s
i
z
e
2
[
j
]
size^2[i]-\sum_{j∈son[i]}size^2[j]
