ARC142D Deterministic Placing

这是一个只用了三个状态的做法，即每个点的状态只有 f_{u,0/1/2}。

首先，我们可以认为 K=2 即一个状态只需要两次的操作唯一就一定是合法的（但是这个东西似乎没有什么作用）。

然后开始手玩，首先对于链的情况，我们相当于是把一条链分成若干个部分，每个部分长度 \ge 2，并且只有两端有一个白点。

比如对于 n=6 一种合法的划分方式就是

现在再来考虑对于这样的一种划分方式染色，也就是让每一条链的端点处存在一个白点。

容易发现

这种情况是不合法的，也就是操作一次之后两条链会合并，那么第二次操作会出现两种情况了。

所以对于 链头与链头 相邻的链，我们一共只有 2 种染色方式（这里 链头 可以理解成链的端点）。

接下来我们把上面的东西拓展到树上面，我们唯一的要求就是划分出来染色之后，移动中不会合并出新的链。

同上理，对于链头和链头相邻的情况，我们最后乘上一个 2 的系数就可以了；

那么接下来就只会去讨论另外两种情况：链头与链中相邻，链中与链中相邻。

对于 链头与链中 相邻，也就是这种情况

其中红色的两条链是我们最开始钦定的两条链。

但是发现你无论如何染色，总有一个时刻上面的链的白点回到上面的一端，那么不管下面的链是什么状态，我们都可以再把树分成图上两条蓝色的链去操作，从而下一次得到的操作就不唯一了。

于是 链头与链中 相邻是不合法的！

最后一种就是 链中与链中 相邻的情况了，画出来就是这样

发现对于这种划分方式，你怎么放白点（怎么染色）都是没有任何影响的，上图中链的状态是不会改变的。

所以上图中的划分一共有 2 \times 2 = 4 中染色方案。

那么接下来就可以 dp 了，上面的分析我们可以看成，我们需要把树分成若干条链，满足每条链的长度 \ge 2，链头和链头相邻，链中与链中相邻。

并且当链中往上转移的时候我们需要乘上 2 的系数，也就是定向的代价。

于是设 f_{u,0/1/2} 表示以 u 为根的子树中：

转移就是看当前的 u 和哪些相邻。

对于 f_{u,0}，我们还需要额外计算 u 一个点为一条链的情况。

那么转移就是

\begin{aligned} f_{u,0} & = \prod_{v } f_{v,1} + \sum_{x} \left( \prod_{v \neq x}2 f_{v,2} \right) f_{x,0} \\ f_{u,1} & = \sum_x \left( \prod_{v \neq x} f_{v,1} \right) f_{x,0} \\ f_{u,2} & = \sum_x \sum_{y \neq x} \left( \prod_{v \neq x, v\neq y} 2f_{v,2} \right) f_{x,0}f_{y,0} \end{aligned}

上面的 x,y,v 都是 u 的儿子。

答案就是 2 \times (f_{1,1} + f_{1,2})，2 是对 1 所在链的连通块定向的方案数。

这样就做完了，时间复杂度线性，代码十分简短，没有分类讨论。代码。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N=2e5+5,H=998244353;
int n,f[N][3];
vector<int> G[N];

int adc(int a,int b){return a+b>=H?a+b-H:a+b;}
int mul(int a,int b){return 1ll*a*b%H;}
void add(int &a,int b){a=adc(a,b);}

void dfs(int u,int fa){
  f[u][0]=1;
  int s0=1,s2=1,t2=0,t0=0;
  for(auto v:G[u]) if(v!=fa){
    dfs(v,u);
    int cur=mul(2,f[v][2]);

    f[u][1]=adc(mul(f[u][1],f[v][1]),mul(f[u][0],f[v][0]));
    f[u][0]=mul(f[u][0],f[v][1]);
    t0=adc(mul(t0,cur),mul(s0,f[v][0]));
    s0=mul(s0,cur);

    f[u][2]=adc(mul(f[u][2],cur),mul(t2,f[v][0]));
    t2=adc(mul(t2,cur),mul(s2,f[v][0]));
    s2=mul(s2,cur);
  }
  add(f[u][0],t0);
}

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;
  for(int i=1,u,v;i<n;i++) cin>>u>>v,G[u].pb(v),G[v].pb(u);
  dfs(1,0);

  cout<<mul(2,adc(f[1][1],f[1][2]));
  return 0;
}