题目链接
解析
数数题，考虑 dp。
考虑树形 dp，发现状态设不出来，因为选叶子的过程是在各个子树之间横跳的，设一个只包含一个子树内信息的状态显然无法解决问题。
然后发现状态更设不出来了，返回去找性质。于是发现一个结论：在操作过程中，在加入当前选中叶子 \(x\) 到 \(S\) 后，\(x = S_{\max}\)，也就是说 \(x\) 是单调不减的。这也意味着 \(x\) 想要被选，必须要求 \(S\) 中的最大值 \(S_{\max} \le x\)。
要想选中 \(x\)，还需要 \(x\) 变为叶子，即以 \(x\) 为根，将其儿子删到只留下一个，根据上一条结论，删掉的结点中，其最大编号应当小于 \(x\)。由于有结点 \(n\) 的存在，如果 \(n\) 变为叶子就会把其它结点全部删完。所以如果 \(x\neq n\) 能被选中，那么留下来的那个儿子的子树必定是 \(n\) 所在的子树。直接令 \(n\) 为根，就只用看所有儿子子树内编号最大值了。
设 \(f_i\) 表示操作过程中以 \(i\) 为最大值的不同 \(S\) 个数，\(g_i\) 表示 \(i\) 的儿子的子树内结点编号最大值。在 \(i\) 加入前，\(S_{\max} < i\)，同时由于有 \(g_i\) 的存在，为了删掉 \(g_i\) 及编号更小的点，需要有 \(S_{\max} > g_i\)。据此，可列出状态转移方程：
注意 \(n\) 是例外的，因为 \(n\) 为根，其能被选时，即度为 \(1\) 时可以连接着一棵子树，这棵子树必定为 \(n - 1\) 所在子树。故改变 \(g_n\) 定义，求 \(g_n\) 时避开 \(n - 1\) 所在子树。
对 \(f\) dp 的时候求前缀和，转移时差分即可做到 \(O(n)\) 的时间复杂度。
代码
转移时注意判 \(g_i < i\)。
/*
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 2e5 + 5,M = 10 + 5,L = 19,L2 = 17,mod = 998244353;
vector<int> t[N];
int f[N],g[N],pre[N];
int mx;
void dfs(int x,int f){for(int nx : t[x])if(nx != f){dfs(nx,x);g[x] = max({g[x],g[nx],nx}); }if(t[x].size() == 1){mx = max(mx,x);}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);int T;cin>>T;while(T--){int n;cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;t[u].push_back(v);t[v].push_back(u);}dfs(n,0);g[n] = 0;for(int nx : t[n]){if(max(g[nx],nx) != n - 1){g[n] = max(g[n],max(g[nx],nx));}}f[mx] = 1;pre[mx] = 1;for(int i=mx + 1;i<=n;i++){if(g[i] < i)f[i] = (pre[i - 1] + mod - pre[g[i]]) % mod;pre[i] = (pre[i - 1] + f[i]) % mod;}cout<<f[n]<<'\n';for(int i=0;i<=n;i++){t[i].clear(); f[i] = pre[i] = g[i] = 0;}mx = 0;}return 0;
}