P6803 星际迷航 题解
题目大意
给定一颗 \(N\) 个节点的树。这样的树有 \(D+1\) 层，编号从 \(0\) 到 \(D\)。对于 \(i=0,1,\dots,D-1\)，需要选择第 \(i\) 层的任意一个节点向第 \(i+1\) 层的任意一个节点连一条有向边。最初人在第 \(0\) 层图的 \(1\) 号节点。两个玩家交替选择下一步向哪走，要求走到的点 \(v\) 之前没有到过，且与当前节点 \(u\) 相邻或有一条有向边从 \(u\) 指向 \(v\)。如果到一个玩家选择时，不能走到任何没有到过的节点，这个玩家就输了。问有多少种连有向边的方案能使得先手必胜。
Solve
首先，如果从一棵树的节点 \(u\) 开始走，那么将这棵树的根定为 \(u\) 之后，走出的合法路径一定是一条从浅往深走的链。所以如果第 \(i\) 层和第 \(i+1\) 层间的有向边指向节点 \(u\)，那么相当于把第 \(i+1\) 层的树的根定为 \(u\)。
连接这条有向边之后，会根据节点 \(u\) 是必胜还是必败，对这条边起点的状态做出一定修改。所以，我们并不关心这条有向边指向的是哪个节点，只关心从指向的那个节点开始，先手是必胜还是必败。
由此，我们设计如下状态：设 \(f(i,1/0)\) 表示考虑了 \(i\) 层树，从第 1 棵树的任意节点开始走，使得先手必胜 / 必败，这样的连边的总方案数。
考虑我把在这 \(i\) 层树前面再添一层树（记为第 0 棵树），即把原来的第 1 棵树连在第 0 棵的某个节点下。 \(f(i,0/1)\) 如何转移到 \(f(i+1,0/1)\)？
记新连的这条有向边为 \((u,v)\)。第 \(0\) 棵树的根为 \(s\)。
对于 \(f(i+1,1)\)，我要求最后先手必胜。
- 如果 \(s\) 原本是必胜的，我要求 \((u,v)\) 不能改变 \(s\) 的状态；
- 否则，我要求必须改变 \(s\) 的状态。
对于 \(f(i+1,0)\)，类似。
接下来考虑什么样的 \((u,v)\) 能使 \(s\) 的状态发生改变。显然当这 \(i\) 层树在从 \(v\) 开始时是必胜态时，\((u,v)\) 一定不会改变 \(s\) 的状态，即：\(u\) 只有连向一个必败点，\((u,v)\) 才会改变 \(s\) 的状态。
所以我们设 \(g(s)\) 表示在以 \(s\) 为根时，有多少个节点 \(u\) 满足从 \(u\) 向一个必败点连边后，\(s\) 的状态会发生改变。
如果求出来 \(g(u)\)，我们根据 \(s\) 原本的状态和要转移到的状态的异同，就能知道是否要求 \((u,v)\) 必须改变 \(s\) 的状态，就有了如下状态转移式：
\[f(i+1,1)\longleftarrow\sum\limits_{s=1}^n \begin{cases} g(s)f(i,0),&h(s)=0\\ n(f(i,0)+f(i,1))-g(s)f(i,0).&h(s)=1 \end{cases}\\ f(i+1,0)\longleftarrow\sum\limits_{s=1}^n \begin{cases} g(s)f(i,0),&h(s)=1\\ n(f(i,0)+f(i,1))-g(s)f(i,0).&h(s)=0\\ \end{cases} \]其中，\(h(s)\) 表示在原树中，以 \(s\) 为根是先手必胜还是必败。\(n(f(i,0)+f(i,1))\) 为这 \(i+1\) 层间的总连边方案。
系数为定值，并且 \(i\) 的范围很大，但第二维状态很少，所以考虑矩阵快速幂加速。
求出 \(f(D,0/1)\) 之后，根据 \(h(1)\) 来计算最终答案即可。
\(h\) 的换根比较简单。问题是 \(g\) 怎么求。
先考虑若以 1 为根，如何求 \(g(1)\)，即朴素树形 dp。
设 \(g'_s(u)\) 表示以 \(s\) 为根时，\(u\) 的子树内有多少节点满足向必败点连边后能改变 \(u\) 的状态。分情况讨论。
- 若 \(u\) 子树内必败，那么 \(g'_s(u)\) 即为所有儿子 \(g'\) 的和，再加上 1，即自己直接连向必败点的方案。
- 否则若 \(u\) 的儿子里只有一个必败，那个儿子记为 \(u'\)，那么 \(g'_s(u)=g'_s(u')\)。
至于换根，记 \(w(u,0/1)\) 表示以 \(u\) 为根时，\(u\) 儿子里必败 / 必胜点的 \(g\) 值的和，\(w'_{s}(u,0/1)\) 表示以 \(s\) 为根时，\(u\) 儿子里必败 / 必胜点的\(g\) 值的和。那么 \(g'\) 的转移可以形式化地表示为：
\[g'_s(u)= \begin{cases} w'_s(u,0)+1,&h'_s(u)=0\\ w'_s(u,1),&h'_s(u)=1\\ 0.&\text{Otherwise} \end{cases} \]其中，\(h'(u)\) 表示以 1 为根时，\(u\) 的儿子内必败点个数。之所以弃掉原本必胜 / 必败的意义，是为了方便转移。
接下来考虑如何换根求 \(g(u)\)。
当根从 \(u\) 换到 \(v\) 时，首先要把 \(v\) 的贡献从 \(w(u),h(u)\) 里刨掉得到 \(w'_v(u),h'_v(u)\)，之后根据上面的式子，计算 \(g'_v(u)\)，用 \(h'_v(u),g'_v(u)\) 更新 \(h(v),w(v)\)。
感觉重点在这个 \(w\) 的定义，很巧妙，省去了很多讨论。
Code
void F(int u,int fa)
{
for(int v:e[u])
if(v!=fa)
F(v,u),h[u]+=!h[v],w[u][h[v]>0]+=g[v];
if(h[u]==1) g[u]=w[u][0];
if(!h[u]) g[u]=w[u][1]+1;
}
void G(int u,int fa)//换根
{
if(!h[u]) cnt=-~cnt;
int _h,_g,_w[2];
for(int v:e[u])
if(v!=fa)
{
_w[0]=w[u][0],_w[1]=w[u][1];
_h=h[u]-!h[v];_w[h[v]>0]-=g[v];
if(_h>1) _g=0;
else if(_h) _g=_w[0];
else _g=_w[1]+1;
h[v]+=!_h;w[v][_h>0]+=_g;
if(h[v]>1) g[v]=0;
else if(h[v]) g[v]=w[v][0];
else g[v]=w[v][1]+1;
G(v,u);
}
}
struct mat{矩乘板子}a;
signed main()
{
n=read();m=read();
for(int i=1,u,v;i<n;i=-~i)
u=read(),v=read(),
e[u].push_back(v),e[v].push_back(u);
F(1,0);G(1,0);
for(int i=1;i<=n;i=-~i)//根据换根求得的 g 计算转移矩阵
if(h[i])
add(a.a[0][0],g[i]),
add(a.a[0][1],n-g[i]),add(a.a[1][1],n);
else
add(a.a[0][1],g[i]),
add(a.a[0][0],n-g[i]),add(a.a[1][0],n);
a=a^(m-1);
int x=(1ll*cnt*a.a[0][0]+1ll*(n-cnt)*a.a[1][0])%MOD;
int y=(1ll*cnt*a.a[0][1]+1ll*(n-cnt)*a.a[1][1])%MOD;
if(h[1]) ans=(1ll*n*(x+y)-1ll*g[1]*x)%MOD;//若以 1 为根必胜，我要求不能改变根的状态
else ans=1ll*g[1]*x%MOD;//否则要求必须改变
return printf("%d",ans),0;
}