@[rainygame](/user/804607) 数组名好评
by ran_qwq @ 2023-08-29 15:14:27
>`fuck[100007];`
by XQH0317 @ 2023-08-29 15:19:58
>struct node{
>
> int u,v;
>
>}fuck[100007];
by SJZ2010 @ 2023-08-29 15:28:15
@[rainygame](/user/804607) 结论为：无论用什么数据都 hack 不掉。证明如下：
上面那份代码的原理是以每个节点为起点 x，在其子树中深度搜索所有的 y，直到两点之间节点权值和 $\ge s$，也就是遍历了所有以 x 为起点，权值和 $\le s$ 的路径。那么整个程序遍历了所有权值和 $\le s$ 的路径。
不妨从终点来考虑这些路径。对于一个路径的终点 y，这条路径的起点只能是 y 的祖先。而到 y 的权值和 $\le s$ 的祖先最多有 $s-1$ 个（极端情况为每个节点权值为 $1$），所以权值 $\le s$ 的路径不会超过 $n(s-1)$。
由于程序遍历了所有权值和 $\le s$ 的路径，所以程序的复杂度上界为 $\mathcal O(ns)$，而 $n\le10^5, s\le10^3$，程序是可以跑过去的。
如果真的需要把程序卡的比较慢，应该造一条链，并使所有节点权值为 $1$。
by DaShaber @ 2023-08-29 16:38:39
@[caibyte](/user/392304) 他是以递归形式实现的，可以卡掉吗？
by rainygame @ 2023-08-29 18:15:17
@[caibyte](/user/392304) 而且他是有重复搜索的，并不能说是遍历。
by rainygame @ 2023-08-29 18:18:12
@[rainygame](/user/804607) 重复搜索是指？
首先对于同一个起点，搜索的终点不会重复，因为题目给出的边是单向（从父亲到儿子）的，从一个点开始搜索能不重不漏地遍历它的子孙；
其次同一个起点所搜索到的权值和 $\le s$ 的路径也不会重复，因为这个起点与每个终点都能唯一地确定一条路径。
by DaShaber @ 2023-08-29 19:41:31
以下图中的树为例（所有节点权值均为 $1$，$s=3$）：
- 执行 `dfs(1,1)`，相当于钦定节点 1 为起点。
- 执行 `dfs(2,2)`，相当于遍历了路径 $1\to 2$。
1. 执行 `dfs(3,3)`，相当于遍历了路径 $1\to 3$，此时 $dis=3$，答案加 $1$ 并返回。
1. 执行 `dfs(4,3)`，相当于遍历了路径 $1\to 4$，此时 $dis=3$，答案加 $1$ 并返回。
- 执行 `dfs(2,1)`，相当于钦定节点 2 为起点。
- 执行 `dfs(3,2)`，相当于遍历了路径 $2\to 3$。
1. 执行 `dfs(5,3)`，相当于遍历了路径 $2\to 5$，此时 $dis=3$，答案加 $1$ 并返回。
1. 执行 `dfs(6,3)`，相当于遍历了路径 $2\to 6$，此时 $dis=3$，答案加 $1$ 并返回。
- 执行 `dfs(4,2)`，相当于遍历了路径 $2\to 4$。
1. 执行 `dfs(7,3)`，相当于遍历了路径 $2\to 7$，此时 $dis=3$，答案加 $1$ 并返回。
- 执行 `dfs(3,1)`，相当于钦定节点 3 为起点......
可以发现每次 dfs 都相当于访问了一条路径，且这些路径长度都 $\le s$。
整个算法遍历的路径有：
$1\to2,1\to3,1\to4,2\to3,2\to5,2\to6,2\to4,2\to7,3\to5,3\to6,4\to7$。
以终点分类：
- 以 $2$ 为终点：${\color{red}1}\to2$
- 以 $3$ 为终点：${\color{red}1}\to3,{\color{red}2}\to3$
- 以 $4$ 为终点：${\color{red}1}\to4,{\color{red}2}\to4$
- 以 $5$ 为终点：${\color{red}2}\to5,{\color{red}3}\to5$
- 以 $6$ 为终点：${\color{red}2}\to6,{\color{red}3}\to6$
- 以 $7$ 为终点：${\color{red}2}\to7,{\color{red}4}\to7$
标红的正是与对应终点之间权值和 $\le s$ 的终点的祖先，对于每个终点数量不会超过 $s-1$。
by DaShaber @ 2023-08-29 20:04:02
@[caibyte](/user/392304) 就比如说上图 1 结点和 2 结点的搜索都有一大部分是重复的，且这些重复部分远远超过了 $s$。
这个是否可以 hack？
by rainygame @ 2023-08-29 22:21:09
先放张图在这，明天打完模拟赛解释一下（
by DaShaber @ 2023-08-29 22:40:33