题意
给定一棵边权为(1)的树，初始棋子在(1)上，第一步必须得移动，往后走的每一步都得比上一次走的距离要严格长，求有多少个包含(1)的连通块是先手必胜的方案数。(nle 10^6)
做法
考虑什么时候先手必胜。
是一条链时
- 若为奇数且根节点在中间，则先手不管往哪移后手都给移动到对面去，这样先手必输
- 若为奇数且根节点不在中间，则先手移到中间，这样先手必胜
- 若为偶数，则开始将点移到较其更远的中点之一，然后跟上面一样，这样先手必胜
是一棵树时，同理可以推广
- 先手必输时直径为奇数且根节点在中点
- 先手必胜：根节点最深子树与次深子树深度不一样
下面代码是这里的：Cold_Chair的博客
code
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int mo = 998244353;
const int N = 1e6 + 5;
int n, x, y;
int fi[N], nt[N * 2], to[N * 2], tot;
void link(int x, int y) {
nt[++ tot] = fi[x], to[tot] = y, fi[x] = tot;
}
int t[N], t0;
void Init() {
scanf("%d", &n);
fo(i, 1, n - 1) {
scanf("%d %d", &x, &y);
link(x, y); link(y, x);
}
}
int md[N], fa[N], son[N];
void bfs() {
t[t0 = 1] = 1;
for(int i = 1; i <= t0; i ++) {
int x = t[i];
for(int j = fi[x]; j; j = nt[j]) if(to[j] != fa[x]) {
fa[to[j]] = x;
t[++ t0] = to[j];
}
}
fd(i, t0, 1) {
int x = t[i];
for(int j = fi[x]; j; j = nt[j]) if(to[j] != fa[x]) {
int y = to[j];
md[x] = max(md[x], md[y] + 1);
if(md[y] > md[son[x]]) son[x] = y;
}
}
}
ll fv[N * 2], *f[N], gv[N * 2], *g[N];
int d[N], d0, us;
void build() {
fo(x, 1, n) if(son[fa[x]] != x) {
d[d0 = 1] = x;
for(int i = 1; i <= d0; i ++)
if(son[d[i]]) d[++ d0] = son[d[i]];
fo(i, 1, d0) f[d[i]] = fv + (us + i), g[d[i]] = gv + (us + i);
us += d0 + 1;
}
}
void xc(int x, int d) {
fo(i, 0, d) {
g[x][i + 1] = g[x][i + 1] * g[x][i] % mo;
f[x][i] = f[x][i] * g[x][i] % mo;
g[x][i] = 1;
}
}
ll sa[N], sb[N];
void dp() {
fd(i2, t0, 2) {
int x = t[i2];
f[x][0] = 1;
for(int ii = fi[x]; ii; ii = nt[ii]) if(to[ii] != fa[x] && to[ii] != son[x]) {
int y = to[ii];
xc(x, md[y] + 1); xc(y, md[y]);
sa[0] = sb[0] = 1;
fo(i, 1, md[y] + 1) {
sa[i] = (sa[i - 1] + f[x][i]) % mo;
sb[i] = (sb[i - 1] + f[y][i - 1]) % mo;
}
f[x][0] = 1;
fo(i, 1, md[y] + 1) f[x][i] = (sa[i] * sb[i] - sa[i - 1] * sb[i - 1] % mo + mo) % mo;
g[x][md[y] + 2] = g[x][md[y] + 2] * sb[md[y] + 1] % mo;
}
}
}
ll p[N], q[N];
int ky[N];
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
Init();
md[0] = -1;
bfs();
build();
fo(i, 0, 2 * n) gv[i] = 1;
dp();
ll ans = 0;
d0 = 0;
for(int i = fi[1]; i; i = nt[i]) {
int y = to[i];
d[++ d0] = y;
xc(y, md[y]);
}
ll s1 = 1;
fo(w, 0, md[1] - 1) {
p[0] = 1; q[d0 + 1] = 1;
fo(i, 1, d0) {
int x = d[i];
p[i] = p[i - 1] * (w == 0 ? 1 : f[x][w - 1]) % mo;
}
fd(i, d0, 1) {
int x = d[i];
q[i] = q[i + 1] * (w == 0 ? 1 : f[x][w - 1]) % mo;
ans = (ans + f[x][w] * p[i - 1] % mo * q[i + 1] % mo * s1) % mo;
f[x][w] = ((w ? f[x][w - 1] : 1) + f[x][w]) % mo;
ky[i] = md[x] > w;
}
int D = d0; d0 = 0;
fo(i, 1, D) if(ky[i])
d[++ d0] = d[i]; else s1 = s1 * f[d[i]][md[d[i]]] % mo;
}
ans = (ans % mo + mo) % mo;
pp("%lld
", ans);
}