(mathcal{Description})
Link.
A B 两人在树上博弈，初始时有一枚棋子在结点 (1)。由 A 先操作，两人轮流移动沿树上路径棋子，且满足本次移动的树上距离严格大于上次的，无法移动者负。先给定一棵含 (n) 个结点的树，求包含结点 (1) 且使得 B 必胜的联通块数量。
(nle2 imes10^5)。
(mathcal{Solution})
结论对了正解写了细节萎了暴力分都没了 qwq……
结论：联通块满足条件，当且仅当其中最深的叶子们不同时属于结点 (1) 的某棵子树。当然也能说作，结点 (1) 是联通块直径的中点。
证：略。
“不同时属于”不太优美，考虑用所有方案减去非法方案。对于结点 (1) 的每棵子树，分别做长剖求出 (f(v,d)) 表示以 (v) 为根，最深叶子深度恰为 (d) 的联通块个数。随后钦定某棵子树取 (d)，其余子树取严格小于 (d) 的方案，即能求出答案。
复杂度 (mathcal O(n))（其实我写得比较难看，会有一个求逆元的 (log) awa……）
(mathcal{Code})
/* Clearink */
#include <list>
#include <cstdio>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
typedef std::pair<int, int> PII;
#define fi first
#define se second
inline int rint() {
int x = 0, s = getchar();
for ( ; s < '0' || '9' < s; s = getchar() );
for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );
return x;
}
const int MAXN = 2e5, MOD = 998244353;
int n, ecnt, head[MAXN + 5];
int mxd[MAXN + 5], son[MAXN + 5];
PII *top, pool[MAXN * 5 + 10], *f[MAXN + 5];
// second 是乘法标记，转移过程中涉及到对长链的后缀乘法，需要打标记。
// 其实呢，由于出题人*****，更新时直接遍历长链也能过√
struct Edge { int to, nxt; } graph[MAXN * 2];
std::list<int> rt;
inline int sub( int a, const int b ) { return ( a -= b ) < 0 ? a + MOD : a; }
inline int add( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }
inline int mul( const long long a, const int b ) { return int( a * b % MOD ); }
inline int mpow( int a, int b ) {
int ret = 1;
for ( ; b; a = mul( a, a ), b >>= 1 ) ret = mul( ret, b & 1 ? a : 1 );
return ret;
}
inline void link( const int u, const int v ) {
graph[++ecnt] = { v, head[u] }, head[u] = ecnt;
graph[++ecnt] = { u, head[v] }, head[v] = ecnt;
}
inline PII* alloc( const int len ) {
PII* ret = top; top += len + 3;
return ret;
}
inline int init( const int u, const int fa ) {
int ret = 1;
mxd[u] = son[u] = 0;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) != fa ) {
ret = mul( ret, add( init( v, u ), 1 ) );
if ( mxd[u] < mxd[v] + 1 ) mxd[u] = mxd[son[u] = v] + 1;
}
}
// printf( "! all(%d)=%d
", u, ret );
return ret;
}
inline void pushad( const int u, const int i, const int v ) {
f[u][i].fi = mul( f[u][i].fi, v );
if ( f[u][i].se ) f[u][i].se = mul( f[u][i].se, v );
else f[u][i].se = v;
}
inline void pushdn( const int u, const int i ) {
if ( f[u][i].se ) {
if ( i < mxd[u] ) pushad( u, i + 1, f[u][i].se );
f[u][i].se = 0;
}
}
inline void solve( const int u, const int fa, PII* curf ) {
f[u] = curf != NULL ? curf : alloc( mxd[u] + 1 );
f[u][0].fi = 1;
if ( son[u] ) solve( son[u], u, f[u] + 1 );
pushdn( u, 0 );
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) != fa && v != son[u] ) {
solve( v, u, NULL );
int vpre = 0, upre = 1;
rep ( j, 0, mxd[v] ) {
pushdn( v, j ), pushdn( u, j + 1 );
if ( j <= mxd[v] ) vpre = add( vpre, f[v][j].fi );
int t = f[u][j + 1].fi;
f[u][j + 1].fi = add( mul( upre, f[v][j].fi ),
mul( f[u][j + 1].fi, add( vpre, 1 ) ) );
upre = add( upre, t );
}
if ( mxd[v] + 2 <= mxd[u] ) {
pushad( u, mxd[v] + 2, add( vpre, 1 ) );
}
}
}
}
inline void allClear() {
// mxd, son cleared in init.
ecnt = 0;
rep ( i, 1, n ) head[i] = 0;
for ( PII *p = pool; p <= top; *p++ = {} );
top = pool;
}
int main() {
freopen( "game.in", "r", stdin );
freopen( "game.out", "w", stdout );
for ( int T = rint(); T--; ) {
n = rint(), allClear();
rep ( i, 2, n ) link( rint(), rint() );
int all = init( 1, 0 ), del = 0;
for ( int i = head[1], v; i; i = graph[i].nxt ) {
solve( v = graph[i].to, 1, NULL );
rt.push_back( v );
rep ( j, 0, mxd[v] - 1 ) pushdn( v, j );
}
// printf( "! all=%d
", all );
int las = 1;
rep ( i, 0, mxd[1] - 1 ) {
for ( int u: rt ) {
int k = !i ? 1 :
mul( las, mpow( add( f[u][i - 1].fi, 1 ), MOD - 2 ) );
del = add( del, mul( k, f[u][i].fi ) );
if ( i ) f[u][i].fi = add( f[u][i].fi, f[u][i - 1].fi );
}
for ( auto it( rt.begin() ); it != rt.end(); ) {
if ( i ) {
las = mul( las,
mpow( add( f[*it][i - 1].fi, 1 ), MOD - 2 ) );
}
las = mul( las, add( f[*it][i].fi, 1 ) );
if ( mxd[*it] == i ) it = rt.erase( it );
else ++it;
}
}
printf( "%d
", sub( all, del ) );
}
return 0;
}
(mathcal{Details})
也不是说代码能力差吧，为什么我总能写那么长呢。
赛时代码比较狰狞（？）可以理解，但尽量先细致地过一遍代码流程，尽量写下来，确认无误再动手。