题意

给定树，选择点权为 选择边权为 ，计数有几种选择存在一种方法使得按照某种顺序，每次将一条边的两个点缩成一个点，权为对应运算结果，最终剩余一个点权为 。

思路

其实我觉得这题非常套路，要是稍微做的人多一点估计就降蓝了。

考虑怎么缩点，简单想想，肯定是先缩 再缩 ，这样的话第一步缩完 之后只要有一个 就胜利了。

所以我们只需要计数所有 联通块中至少一个全是 的方案数，为了好写我们反过来求所有联通块都不是全 的方案数，然后随便 DP 一下就好了。

CODE

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=100010,FSIZE=1<<24,mo=998244353;
int n;
ll ans,f[N][2];
vector<int> t[N];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;*InF>32;x=x*10+(*InF++^48));
}
void dfs(int x,int fa=0){
    f[x][0]=f[x][1]=1;
    for(int i:t[x]) if(i!=fa){
        dfs(i,x);
        f[x][0]=(f[x][0]*f[i][0]*2+f[x][1]*f[i][0]+f[x][0]*f[i][1])%mo;
        f[x][1]=(f[x][1]*(f[i][0]+f[i][1]))%mo;
    }
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);
    for(int i=1,x,y;i<n;++i){
        read(x);read(y);
        t[x].push_back(y);
        t[y].push_back(x);
    }
    dfs(1);
    for(int i=ans=1;i<=n+n-1;++i) if((ans+=ans)>=mo) ans-=mo;
    printf("%lld\n",(ans-f[1][0]+mo)%mo);
    return(0);
}