Codeforces Round #630 (Div. 2) F. Independent Set 树形dp

链接

显然一颗树的独立集可以很容易的转移过来
dp[u][0]=∏(dp[v][0]+dp[v][1])
dp[u][1]=∏(dp[v][0])
最后答案为dp[1][0]+dp[1][1]
加上子集其实就相当于在转移的时候把当前边断开的贡献加上去就可以了，可以得到
dp[u][0]=∏(dp[v][0]+dp[v][1]+dp[v][0]+dp[v][1])
dp[u][1]=∏(dp[v][0] +dp[v][0]+dp[v][1])
但发现有一种情况是不合法的：改点为状态1，并且其所有子节点都未选。
所以我还需要容斥一下，把这种状态的答案减下去即可。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head
int n,k;
VI G[maxn];
LL f[maxn],g[maxn],h[maxn];
void dfs(int u,int fa){
    f[u]=g[u]=h[u]=1;
    for(int v:G[u]){
        if(v==fa) continue;
        dfs(v,u);
        LL tot=(f[v]+g[v]-h[v])%mod;
        f[u]=f[u]*(tot+g[v])%mod;
        g[u]=g[u]*(f[v]+g[v]+tot)%mod;
        h[u]=h[u]*tot%mod;
    }
    //printf("%d :(%lld %lld %lld)\n",u,f[u],g[u],h[u]);
}
int main(){
      scanf("%d",&n);
      for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(v),G[v].pb(u);
      }
      dfs(1,-1);
      printf("%lld\n",((f[1]+g[1]-h[1]-1)%mod+mod)%mod);
}