设
f
(
x
,
d
)
f(x,d)
f(x,d)表示距离
x
x
x小于等于
d
d
d的点的集合
如果
f
(
x
,
d
1
)
=
f
(
y
,
d
2
)
f(x,d1)=f(y,d2)
f(x,d1)=f(y,d2)
那么对于任意
x
→
y
x\to y
x→y路径上的点
z
z
z，存在
d
d
d满足
f
(
z
,
d
)
=
f
(
x
,
d
1
)
=
f
(
y
,
d
2
)
f(z,d)=f(x,d1)=f(y,d2)
f(z,d)=f(x,d1)=f(y,d2)
并且
d
d
d值是呈
V
V
V型的（真的好难证 qwq
证明可以考虑
f
(
x
,
d
)
f(x,d)
f(x,d)的唯一性
那么对于若干同构的
f
(
x
,
d
)
f(x,d)
f(x,d)，我们只在
d
d
d值最小处计数
如果
d
d
d是最小的，那么应该满足对于任意与
x
x
x相邻的
y
y
y，
f
(
x
,
d
)
≠
f
(
y
,
d
−
1
)
f(x,d)\ne f(y,d-1)
f(x,d)=f(y,d−1)
设
s
z
[
x
]
sz[x]
sz[x]表示从
x
x
x出发最长链长度，
s
z
2
[
x
]
sz2[x]
sz2[x]表示从
x
x
x出发次长链的长度
m
x
[
x
]
mx[x]
mx[x]表示节点
x
x
x最大的合法的
d
d
d
那么
m
x
[
x
]
=
min
(
s
z
[
x
]
−
1
,
s
z
2
[
x
]
+
1
)
mx[x]=\min(sz[x]-1,sz2[x]+1)
mx[x]=min(sz[x]−1,sz2[x]+1)
答案是
∑
(
m
x
[
x
]
+
1
)
+
1
\sum{(mx[x]+1)}+1
∑(mx[x]+1)+1
如果只有一部分点能作为根呢
考虑对于那些最小的
d
d
d，找到一个最优秀的替代点
不难发现
d
d
d具有单调性
设
l
w
[
x
]
lw[x]
lw[x]表示节点
x
x
x最小的能找到替代点
d
d
d
如果
f
(
x
,
d
)
f(x,d)
f(x,d)能找到替代点，则存在与
x
x
x相邻的
y
y
y，满足
f
(
x
,
d
)
=
f
(
y
,
d
+
1
)
f(x,d)=f(y,d+1)
f(x,d)=f(y,d+1)
那么
l
w
[
x
]
=
min
y
∈
s
o
n
[
x
]
(
max
(
s
z
[
y
]
+
1
,
l
w
[
y
]
−
1
)
)
lw[x]=\min_{y\in son[x]}(\max(sz[y]+1,lw[y]-1))
lw[x]=miny∈son[x](max(sz[y]+1,lw[y]−1))
显然我们需要换根
然后就做完了
答案是
∑
(
m
x
[
x
]
−
l
w
[
x
]
+
1
)
+
1
\sum(mx[x]-lw[x]+1)+1
∑(mx[x]−lw[x]+1)+1
复杂度
O
(
n
)
O(n)
O(n)
Division into Two
振作起来
巧妙的限制转化
不妨将任意方案抽象成一个
01
01
01序列
直接转移比较恶心
毋宁放弃直接转移
不妨设
A
≥
B
A\ge B
A≥B
首先根据鸽巢原理，对于任意
i
≥
3
i\ge 3
i≥3 有
s
[
i
]
−
s
[
i
−
2
]
≥
B
s[i]-s[i-2]\ge B
s[i]−s[i−2]≥B
有了这个性质就可以转移了
d
p
[
i
]
dp[i]
dp[i]表示前
i
i
i个数，第
i
i
i个数在
X
X
X集合中的方案数