【题解】CF1332F

纪念第一道自己写出来的 *2500

我也不知道是不是自己写出来的 也许以前看过题解但是忘了（x

不妨假设根节点为 $1$。

考虑 $dp$：设 $dp_{i,x,y}$ ( $x,y \in [0,1]$ ) 表示以 $i$ 为根的子树内，是否选 $i$ 上面的边 ( $x$ )，是否选节点 $i$ ( $y$ ) 的答案。

“是否选 $i$ 上面的边”的意思是 连接 $i$ 与 $i$ 的父节点的边 是否包括在当前这个边导出子图中。

“是否选节点 $i$”的意思是节点 $i$ 是否包括在当前这个点独立集中。

考虑转移：

$dp_{i,0,0}=\prod\limits_{j\in son_i} dp_{j,0,0}+dp_{j,0,1}+dp_{j,1,0}+dp_{j,1,1} \\ dp_{i,1,0}=\prod\limits_{j\in son_i} dp_{j,0,0}+dp_{j,0,1}+dp_{j,1,0}+dp_{j,1,1} \\ dp_{i,1,1}=\prod\limits_{j\in son_i} dp_{j,0,0}+dp_{j,0,1}+dp_{j,1,0}$

$dp_{i,0,1}$ 的转移稍微复杂一点：

$dp_{i,0,1}=\left(\prod\limits_{j\in son_i} dp_{j,0,0}+dp_{j,0,1}+dp_{j,1,0}\right) - \left( \prod\limits_{j\in son_i} dp_{j,0,1}+dp_{j,0,0} \right)$

如果节点 $i$ 在子图中，而这个点 $i$ 上方的边又不在子图中，那么需要它的一个子节点提供一条边使得它在子图中。于是考虑补集转化，用总方案数减去没有边连向节点 $i$ 的方案数，即得到上式。

注意题目中给出的是 非空 边导出子图，最后答案要减一。

// 2020.11.22
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define debug puts("QwQ");
inline int read(){
    int x=0,f=1;
    char ch;
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return f*x;
}

const int MAXN=300005;
const int MOD=998244353;
int n;
vector<int> v[MAXN];
int dp[MAXN][2][2];
//          边　点
bool vis[MAXN];

void dfs(int p){
	// 选点选边：选点不选边 / 选边不选点 / 不选边不选点
	// 不选点选边：选点不选边 / 选边不选点 / 不选边不选点 / 选点选边
	// 不选点不选边：选点不选边 / 选边不选点 / 不选边不选点 / 选点选边
	// 选点不选边：选点不选边 / 选边不选点 / 不选边不选点 - 选点不选边 / 不选边不选点
	vis[p]=true;
	int cnt1=1,cnt2=1,cnt0=1;
	for (int i:v[p]){
		if (vis[i]) continue;
		dfs(i);
		cnt1=cnt1*(dp[i][0][1]+dp[i][0][0]+dp[i][1][0])%MOD;
		cnt2=cnt2*(dp[i][0][1]+dp[i][0][0]+dp[i][1][0]+dp[i][1][1])%MOD;
		cnt0=cnt0*(dp[i][0][1]+dp[i][0][0])%MOD;
	}

	dp[p][1][0]=dp[p][0][0]=cnt2;
	dp[p][1][1]=cnt1;
	dp[p][0][1]=(cnt1-cnt0+MOD)%MOD;
}

signed main()

{
	n=read();
	for (int i=1;i<n;i++){
		int x=read(),y=read();
		v[x].push_back(y);
		v[y].push_back(x);
	}

	dfs(1);
	cout<<((dp[1][0][1]+dp[1][0][0]+MOD-1)%MOD)<<endl;
	return 0;
}