F. Independent Set

题意：

all the vertices in the original graph that are incident on at least one edge in the subgraph.这句话不太理解

edge-induced subgraph(诱导子图)

求出所有诱导子图的独立点集的个数和

分析：

这题想到是$dp$，但是一直没有想好怎么做，看了题解才明白的

定义$dp[u][0]$为u节点不被涂色并且$u$作为根节点的方案数，定义$dp[u][1]$为$u$节点被涂色并且$u$作为根节点的方案数

定义$dp[u][2]$为$u$作为根节点并且它和子树的边都被切断的方案数

$dp[u][2]=\prod_{v}(dp[v][0]+dp[v][1]-2*dp[v][2]+dp[v][2])$

$dp[u][1]=\prod_{v}(2*dp[v][0]+dp[v][1]-2*dp[v][2]+dp[v][2])$

$dp[u][0]=\prod_{v}(2*dp[v][0]+2*dp[v][1]-2*dp[v][2]+dp[v][2])$

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(b);i>=(a);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> PII;

const ll mod=998244353 ;
const int maxn=3e5+7;
VI ve[maxn];
ll dp[maxn][4];
int n;
void dfs(int x,int fa){
	dp[x][0]=dp[x][1]=dp[x][2]=1;
	for(auto v:ve[x]){
		if(v==fa)continue;
		dfs(v,x);
		dp[x][2]=dp[x][2]*(dp[v][0]+dp[v][1]-dp[v][2]+mod)%mod;
		dp[x][1]=dp[x][1]*(dp[v][0]*2+dp[v][1]-dp[v][2]+mod)%mod;
		dp[x][0]=dp[x][0]*(dp[v][0]*2+dp[v][1]*2-dp[v][2]+mod)%mod;
	}
}
int main() {
	scanf("%d",&n);
	rep(i,1,n-1){
		int a,b;
		scanf("%d %d",&a,&b);
		ve[a].pb(b);
		ve[b].pb(a);
	}
	dfs(1,-1);
	// rep(i,1,n)cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<endl;
	printf("%lld\n",(dp[1][0]+dp[1][1]-dp[1][2]+mod-1)%mod);
    return 0;
}

　　

#include <bits/stdc++.h>using namespace std;#define rep(i,a,b) for (int i=(a);i<=(b);i++)#define per(i,a,b) for (int i=(b);i>=(a);i--)#define pb push_back#define mp make_pair#define fi first#define se second#define SZ(x) ((int)(x).size())
typedef long long ll;typedef vector<int> VI;typedef pair<int,int> PII;
const ll mod=998244353 ;const int maxn=3e5+7;VI ve[maxn];ll dp[maxn][4];int n;void dfs(int x,int fa){dp[x][0]=dp[x][1]=dp[x][2]=1;for(auto v:ve[x]){if(v==fa)continue;dfs(v,x);dp[x][2]=dp[x][2]*(dp[v][0]+dp[v][1]-dp[v][2]+mod)%mod;dp[x][1]=dp[x][1]*(dp[v][0]*2+dp[v][1]-dp[v][2]+mod)%mod;dp[x][0]=dp[x][0]*(dp[v][0]*2+dp[v][1]*2-dp[v][2]+mod)%mod;}}int main() {scanf("%d",&n);rep(i,1,n-1){int a,b;scanf("%d %d",&a,&b);ve[a].pb(b);ve[b].pb(a);}dfs(1,-1);// rep(i,1,n)cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<endl;printf("%lld\n",(dp[1][0]+dp[1][1]-dp[1][2]+mod-1)%mod);    return 0;}