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

为根的子树中：

$f_{u,0}$ 表示 $u$ 目前是一条往上的链的链头，但是其实并不合法，我们还需要往上继续拓展的方案数（即 $u$ 是最终的一条链的链中）。
$f_{u,1}$ 表示 $u$ 是一条完整的合法链的链头的方案数。
$f_{u,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

所在链的连通块定向的方案数。

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

CPP

#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;
}

ARC142D Deterministic Placing

文章操作

相关推荐

评论

ARC142D Deterministic Placing