题目大意

给一棵 $n$ 个点的树和一个空集合 $S$ 。每一步先找到当前树上编号最大的叶子 $x$ ，把 $x$ 加入 $S$ ，然后可以任选另一个叶子删掉。重复 $n-1$ 次，问最后可能得到多少个不同的集合 $S$ 。

输入有多组测试，所有测试的 $n$ 之和不超过 $2\cdot 10^5$ 。答案对 $998244353$ 取模。

思路讲解

一句话

把树以最大编号点 $n$ 为根，非根点 $y$ 能被当前最大叶子 $x$ 转移到，当且仅当 $need[y] < x < y$ ；根节点单独处理，答案是所有能压住其它根分支的 $dp[x]$ 之和。

状态怎么想

集合 $S$ 的出现顺序一定是严格递增的一条链：当前最大叶子是 $x$ ，下一次进入 $S$ 的点只能是某个更大的 $y$ 。因此可以定义：

1	dp[y] = 最后一个进入 S 的点是 y 的方案数

初始状态不是 $1$ ，而是原树里的最大叶子：

1 2	start = max { v \| degree(v) == 1 } dp[start] = 1

这里有一个很容易错的坑：不能用“以 $n$ 为根后的有根树叶子”来找 start。如果根本身是原树叶子，它就是一开始的最大叶子。

非根转移

对一个非根点 $y$ ，设：

1	need[y] = y 的所有儿子子树里的最大编号

若当前最大叶子是 $x$ ，想让 $y$ 成为下一次最大叶子，需要先把 $y$ 下方所有分支删到不会冒出比 $x$ 更大的点。因此条件就是：

1	need[y] < x < y

所以转移可以一次性写成区间和：

1	dp[y] = sum dp[x], x in [need[y] + 1, y - 1]

这里不需要再扣掉 subtree(y)。因为如果 $x$ 在 $y$ 的子树里，那么 $x$ 一定被 need[y] 覆盖，和 need[y] < x 矛盾。

根节点转移

根 $n$ 没有父亲方向，所以不能套普通点的公式。根的每个儿子对应一条根分支，定义：

1	branchMax[v] = max(v, subTreeMx[v])

也就是这个根儿子分支里的最大编号。设所有根分支最大值里的第二大值是 secondMax。想让根成为下一次最大叶子，只需要当前 $x$ 压住所有其它分支：

1	x > secondMax

所以根的贡献是：

1	dp[root] = dp.query(secondMax + 1, root - 1)

注意 secondMax 是门槛，不是前驱点。不要写成查 dp[secondMax]，也不要查最大根儿子本身。

这次踩过的坑

start 要从原树度数为 $1$ 的点里取最大值，不能从有根树叶子里取。
维护最大值和次大值时，新最大值出现后，旧的最大值必须下放成次大值。
根转移看的是第二大的根分支最大值，不是根的最大邻居，也不是最大分支的根儿子。
modint 不能直接用 std::max，因为模意义下比较大小没有自然语义。
BIT 支持 0-based 调用时，最好先把外部下标统一 normalize 到内部 1-based，再统一裁剪到 [1,n]。

Hack 例子

初始叶子如果算错，会被这组打掉：

正确答案是 1，因为最大叶子一开始就是根 5。

根转移如果只看最大邻居或最大根儿子，会被这组打掉：

正确答案是 2，对应集合 {3,6} 和 {3,4,6}。

因为 3,4 都可以转移（3 可以转移的原因在下面）

1 2	// * 只要能够压制其他子树的值（mx2），那么即可向 n 转移 // * 因为可以借刀杀人，借 n 的手，把自己子树中的其他值给干掉

AC 代码

AC 提交链接

本地代码已 AC；完整源码折叠在下面。

展开 AC 本地源码

// teamname: Gospel_rock
/**
 * Problem: E. Deconstruction Tree
 * URL:     https://codeforces.com/contest/2229/problem/E
 * Limits:  2000 ms / 256 MB
 * Author:  Gospel_rock
 * My blog: https://znzryb.com/
 *
 * Powered by cph-ng (https://github.com/langningchen/cph-ng)
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)

using namespace std;

#if 1 && defined(LOCAL)
// clang-format off
// @formatter:off
namespace DBG {
	template<typename T> void debug(T x);
	void debug(bool x);
	void debug(string x);
	template<typename T> void debug(vector<T> v);
	template<typename T, size_t N> void debug(array<T, N> v);
	template<typename T> void debug(set<T> s);
	template<typename T, typename U> void debug(pair<T, U> p);
	template<typename T, typename U> void debug(map<T, U> m);
	template<typename, typename = void> constexpr bool _has_iter_v = false;
	template<typename T> constexpr bool _has_iter_v<T, void_t<decltype(declval<T>().begin()), decltype(declval<T>().end())>> = true;
	template<typename T>
	void debug(T x) { cerr << x; } void debug(bool x) { cerr << (x ? "T" : "F"); } void debug(string x) { cerr << '"' << x << '"'; }
	template<typename T> void debug(vector<T> v) { constexpr bool nested = _has_iter_v<T>; int n = v.size(); cerr << "["; for (int i = 0; i < n; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (n) cerr << "\n"; } cerr << "]"; }
	template<typename T, size_t N> void debug(array<T, N> v) { constexpr bool nested = _has_iter_v<T>; cerr << "["; for (size_t i = 0; i < N; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (N) cerr << "\n"; } cerr << "]"; }
	template<typename T> void debug(set<T> s) { cerr << "{"; int f = 0; for (auto x: s) { if (f++) cerr << ", "; debug(x); } cerr << "}"; }
	template<typename T, typename U> void debug(pair<T, U> p) { cerr << "("; debug(p.first); cerr << ", "; debug(p.second); cerr << ")"; }
	template<typename T, typename U> void debug(map<T, U> m) { cerr << "{"; int f = 0; for (auto &[k, v]: m) { if (f++) cerr << ", "; debug(k); cerr << ": "; debug(v); } cerr << "}"; }
	void _dbg() { cerr << endl; }
	template<typename T, typename... A> void _dbg(T x, A... a) { debug(x); if (sizeof...(a)) cerr << ", "; _dbg(a...); }
}
// clang-format on
// @formatter:on
#define dbg(x...) cerr << "[" << setw(7) << #x << "] = ", DBG::_dbg(x)
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"
#define myAssert(...) assert((__VA_ARGS__))
#else
#define dbg(x...) 11
#define cend 45
#define cEnd 14
#define myAssert(x) 14
#endif

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353;  // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/**
 * 
 * 
 */
// T: 底层存储类型 (uint32_t / uint64_t)
// MOD: 模数
// Wide: 乘法时用的更宽类型
template <class T, T MOD, class Wide = ull>
struct modint {
	T v;
	modint(ll x = 0) {
		ll t = x % (ll)MOD;
		if (t < 0) t += MOD;
		v = (T)t;
	}

	T val() const { return v; }

	modint& operator+=(const modint& o) {
		T x = v + o.v;
		if (x >= MOD) x -= MOD;
		v = x;
		return *this;
	}

	modint& operator-=(const modint& o) {
		T x = v >= o.v ? v - o.v : (T)(v + MOD - o.v);
		v = x;
		return *this;
	}

	modint& operator*=(const modint& o) {
		Wide t = (Wide)v * (Wide)o.v;
		v = (T)(t % MOD);
		return *this;
	}

	// 幂
	static modint powmod(modint a, ll e) {
		modint r = 1;
		while (e) {
			if (e & 1) r *= a;
			a *= a;
			e >>= 1;
		}
		return r;
	}

	// 逆元（假定 MOD 是质数）
	static modint inv(modint a) {
		return powmod(a, (ll)MOD - 2);
	}

	modint& operator/=(const modint& o) {
		return *this *= inv(o);
	}

	// 一元
	modint operator+() const { return *this; }
	modint operator-() const { return modint(0) - *this; }

	// 二元
	friend modint operator+(modint a, const modint& b) { return a += b; }
	friend modint operator-(modint a, const modint& b) { return a -= b; }
	friend modint operator*(modint a, const modint& b) { return a *= b; }
	friend modint operator/(modint a, const modint& b) { return a /= b; }

	friend bool operator==(const modint& a, const modint& b) { return a.v == b.v; }
	friend bool operator!=(const modint& a, const modint& b) { return a.v != b.v; }

	friend ostream& operator<<(ostream& os, const modint& x) {
		return os << x.v;
	}
	friend istream& operator>>(istream& is, modint& x) {
		ll t;
		if (!(is >> t)) return is;
		x = modint(t);
		return is;
	}
};
using U = modint<uint32_t, mod>;

/* 2026-04-19 luogu 线段树模板题
 * AC https://www.luogu.com.cn/record/274702532
 * 进一步添加了 public,private 规定了接口的可见性
 * 2026-04-19 增强了对 0 的鲁棒性
 * AC https://acm.hdu.edu.cn/contest/view-code?cid=1201&rid=9803
 */
template <typename T>
class BIT {
	// 支持区间修改，区间查询
	// 维护两个差分：d[i] 和 i*d[i]
	// 前缀和 sum(p) = (p+1)*sum(d[1..p])
	//              - sum(i*d[i], 1..p)
	vector<T> tr1, tr2;
	int n;
	bool zeroBased;

	ll lowbit(ll x) {
		return x & (-x);
	}

public:
	enum IndexBase {
		ZeroBased,
		OneBased
	};

	BIT(int n_, IndexBase indexBase) {
		n = n_;
		zeroBased = indexBase == ZeroBased;
		// 这个 n+1 就够了，虽然涉及到这个差分
		tr1.assign(n + 2, 0);
		tr2.assign(n + 2, 0);
	}

private:
	ll normalize(ll p) {
		return zeroBased ? p + 1 : p;
	}

	bool fixRange(ll& l, ll& r) {
		if (l > r) return false;
		l = normalize(l);
		r = normalize(r);
		l = max<ll>(l, 1);
		r = min<ll>(r, n);
		return l <= r;
	}

	void add(vector<T>& tr, ll p, T x) {
		// 防止 0 死循环
		if (p <= 0) return;
		while (p <= n) {
			tr[p] += x;
			p += lowbit(p);
		}
	}

	T sum(vector<T>& tr, ll p) {
		T ret = 0;
		while (p) {
			ret += tr[p];
			p -= lowbit(p);
		}
		return ret;
	}

	// 单点加
	void add(ll p, T x) {
		add(tr1, p, x);
		add(tr2, p, p * x);
	}

public:
	// 区间加，[l, r] 每个位置加 x
	void add(ll l, ll r, T x) {
		if (!fixRange(l, r)) return;
		add(tr1, l, x);
		add(tr1, r + 1, -x);
		add(tr2, l, l * x);
		add(tr2, r + 1, -(r + 1) * x);
	}

private:
	// 前缀和 a[1] + a[2] + ... + a[p]
	T query(ll p) {
		return (p + 1) * sum(tr1, p) - sum(tr2, p);
	}

public:
	// 区间和 a[l] + ... + a[r]
	T query(ll l, ll r) {
		if (!fixRange(l, r)) return 0;
		return query(r) - query(l - 1);
	}
};

// 这道题目不能够采用传统子树的那种树状 dp 的解决方法
// 原因是，你采用了这种方法，会发现状态在子树间乱窜
// 进而导致比较大的问题
void Solve() {
	ll N;
	cin >> N;
	// 计数
	vector<vector<ll>> g(N);
	for (int i = 0; i < N - 1; ++i) {
		ll u, v;
		cin >> u >> v;
		u--;
		v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	// 一个数字 x 能够向一个数字 y 进行转移
	// 其实是因为首先 y>x
	// next subtreeMaxVal(y) < x
	vector<ll> subTreeMx(N);
	// solve subtreeMaxVal
	ll mxLeaf = 0;
	auto dfs = [&](auto&& go, ll u, ll p) -> void {
		for (auto& v : g[u]) {
			if (v == p) continue;
			go(go, v, u);
			subTreeMx[u] = max({subTreeMx[v], subTreeMx[u], v});
		}
	};
	dfs(dfs, N - 1, -1);
	for (int i = 0; i < N; ++i) {
		if (SZ(g[i]) == 1) {
			mxLeaf = max(mxLeaf, (ll)i);
		}
	}
	// ？当然，上面的那个 dp 是 O(n^2) 的
	// ？ 想要变成 O(n) 的，那么就需要不想 x->y 转移，
	// * 而是变成一次性找出所有可以向 y 转移的 x
	// ！这样子想的动机是这个比较复杂的转移信息都是挂在 y 上的，
	// * 那么不妨利用这些信息
	// ？ 如何实现这个转移的顺序，保证不会出现各种奇怪的情况
	// * 可以使用拓扑排序，当然，由于转移本身具有单调性，也可以不使用
	BIT<U> dp(N, BIT<U>::ZeroBased);
	// TODO 实现 subTreeMaxVal(y) < x < y 的所有 x
	// * 这个 x 需要满足的条件就是
	dp.add(mxLeaf, mxLeaf, 1);
	for (int y = mxLeaf + 1; y < N; ++y) {
		if (subTreeMx[y] > y) {
			continue;
		}
		if (y == N - 1) {
			ll mx1 = -1, mx2 = -1;
			for (auto& v : g[y]) {
				ll cur = max(subTreeMx[v], v);
				if (cur > mx1) {
					tie(mx1, mx2) = make_tuple(cur, mx1);
				} else if (cur > mx2) {
					mx2 = cur;
				}
			}
			// * 只要能够压制其他子树的值，那么即可向 n 转移
			// * 因为可以借刀杀人，借 n 的手，把自己子树中的其他值给干掉
			dp.add(y, y, dp.query(mx2 + 1, N - 2));
			continue;
		}
		U allx = dp.query(subTreeMx[y] + 1, y - 1);
		dp.add(y, y, allx);
	}
	U ans = dp.query(N - 1, N - 1);
#ifdef LOCAL
	for (int i = 0; i < N; ++i) {
		cerr << dp.query(i, i) << " ";
	}
	cerr << "\n";
	cend;
#endif
	if (ans == 0) ans = 1;
	cout << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf);  // 无缓冲流，方便我们调试
#endif

	cin >> lT;
	for (testcase = 1; testcase <= lT; ++testcase)
		Solve();
	return 0;
}

/*
AC
https://codeforces.com/contest/2229/submission/376625320

6
/ \
2   5
  / \
 3   4
	/
   1

*/

心路历程（WA，TLE，MLE……）

一开始把转移看成 x -> y 的枚举，感觉红箭头很乱；后来固定终点 $y$ ，发现合法前驱是一段编号区间。
中途误以为还需要扣掉 subtree(y)，后来发现 need[y] < x 已经自动排除了这个情况。
根节点是最容易绕的地方：普通点有父亲方向当退路，根没有，所以必须单独看根分支。
真正让根变简单的是一句话：根转移只看第二大的根分支最大值。
后面写代码时，几个 bug 都来自“把门槛误当成点”：secondMax 是阈值，不是要查的前驱状态。

附件

暂无。后续如果整理成完整 PDF 或动画，可以再补到这里。

Znzryb's Blog

CF 1100 E - Deconstruction Tree