题目大意

一棵树，每个点上有标号，按输入顺序扫每条边，如果边的两端都有标记则把一个删掉并记下来，否则不做处理，问最终记录序列的方案

题解

xjb翻题的时候找到的，之前dyp讲过当时并不知道在讲什么东西之后想了一下

按顺序很关键，否则不太可做

对于一个点来说有3种边，在父亲边前的，父亲边，在父亲边后的

所以设f[i][0/1/2/3]，表示点i做到当前边的时候 不选/通过3类边删了i

按顺序讨论即可，简单自然，这样建出的序列是唯一的

注意只有在处理父亲边的时候才需要决策，其他情况由于子树已经确定了转移也是唯一的

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%998244353
#define mod 998244353
#define ll long long
//#define file
using namespace std;

int A[200001][2],a[400001][2],ls[200001],n,i,j,k,l,len;
ll f[200001][4],F[4]; //no before fa after

void New(int x,int y) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;}
void dfs(int Fa,int t)
{
    bool bz=0;
    int i;

    f[t][0]=1;
    for (i=ls[t]; i; i=a[i][1])
    {
        if (a[i][0]!=Fa)
        {
            dfs(t,a[i][0]);
            memset(F,0,sizeof(F));
            if (!bz)
            {
                add(F[1],f[t][0]*f[a[i][0]][0]);add(F[1],f[t][1]*f[a[i][0]][0]);
                add(F[0],f[t][0]*f[a[i][0]][1]);add(F[1],f[t][1]*f[a[i][0]][1]);
                add(F[0],f[t][0]*f[a[i][0]][2]);
                add(F[1],f[t][0]*f[a[i][0]][3]);add(F[1],f[t][1]*f[a[i][0]][3]);
            }
            else
            {
                add(F[3],f[t][0]*f[a[i][0]][0]);add(F[1],f[t][1]*f[a[i][0]][0]);add(F[2],f[t][2]*f[a[i][0]][0]);add(F[3],f[t][3]*f[a[i][0]][0]);
                add(F[0],f[t][0]*f[a[i][0]][1]);add(F[1],f[t][1]*f[a[i][0]][1]);add(F[2],f[t][2]*f[a[i][0]][1]);add(F[3],f[t][3]*f[a[i][0]][1]);
                add(F[0],f[t][0]*f[a[i][0]][2]);
                add(F[3],f[t][0]*f[a[i][0]][3]);add(F[1],f[t][1]*f[a[i][0]][3]);add(F[2],f[t][2]*f[a[i][0]][3]);add(F[3],f[t][3]*f[a[i][0]][3]);
            }
        }
        else
        {
            memset(F,0,sizeof(F)),bz=1;
            add(F[0],f[t][0]),add(F[2],f[t][0]);
            add(F[1],f[t][1]);
        }
        memcpy(f[t],F,sizeof(F));
    }
}

int main()
{
    #ifdef file
    freopen("cf1276D.in","r",stdin);
    #endif

    scanf("%d",&n);
    fo(i,1,n-1) scanf("%d%d",&A[i][0],&A[i][1]);
    fd(i,n-1,1) New(A[i][0],A[i][1]),New(A[i][1],A[i][0]);

    dfs(0,1);
    printf("%lld\n",(f[1][0]+f[1][1]+f[1][2]+f[1][3])%mod);

    fclose(stdin);
    fclose(stdout);
    return 0;
}