[ARC142D] Deterministic Placing

感觉并不困难。但是为什么又读错题？？？

发现黑点会不断采取反复横跳的方式移动，问题形式形如对整棵树进行若干单向链划分。而黑点沿着单向链移动后，会使单向链反向。单向链的箭头为白点，箭身与箭尾为黑点。讨论一些的情况：

1. 箭尾不能和箭尾相连。
2. 箭头不能和箭头相连。
3. 箭身只能和箭身相连。

于是直接 DP，分讨状态与转移即可。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e5+10,mod=998244353;
template <class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n;
int tot,head[N],ver[N<<1],ne[N<<1];
int f[N][8],g[8];
inline void adj(int &x){x+=x>>31&mod;}
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void dfs(int x,int fa)
{
    f[x][0]=f[x][4]=f[x][6]=1;
    int y;
    auto get=[&](int a,int _a,int b){return adj(f[x][a]+=1ll*g[_a]*f[y][b]%mod-mod);};
    for(int i=head[x];i;i=ne[i])
    {
        if((y=ver[i])==fa)continue;
        dfs(y,x);
        memcpy(g,f[x],sizeof(f[x]));
        memset(f[x],0,sizeof(f[x]));
        get(0,0,3);
        get(1,1,3),get(1,0,4),get(1,0,1);
        get(2,2,3),get(2,0,6),get(2,0,2);
        get(3,3,3),get(3,1,2),get(3,1,6),get(3,2,1),get(3,2,4);
        get(4,4,7);
        get(5,5,7),get(5,4,2),get(5,4,6);
        get(6,6,5);
        get(7,7,5),get(7,6,1),get(7,6,4);
    }
}
int main()
{
    read(n);
    for(int i=1,u,v;i<n;i++)read(u,v),add(u,v),add(v,u);
    dfs(1,0);
    printf("%d\n",((f[1][3]+f[1][5])%mod+f[1][7])%mod);
    return 0;
}