纪念第一道自己写出来的 *2500
我也不知道是不是自己写出来的 也许以前看过题解但是忘了(x
不妨假设根节点为 。
考虑 :设 ( ) 表示以 为根的子树内,是否选 上面的边 ( ),是否选节点 ( ) 的答案。
“是否选 上面的边”的意思是 连接 与 的父节点的边 是否包括在当前这个边导出子图中。
“是否选节点 ”的意思是节点 是否包括在当前这个点独立集中。
考虑转移:
的转移稍微复杂一点:
如果节点 在子图中,而这个点 上方的边又不在子图中,那么需要它的一个子节点提供一条边使得它在子图中。于是考虑补集转化,用总方案数减去没有边连向节点 的方案数,即得到上式。
注意题目中给出的是 非空 边导出子图,最后答案要减一。
// 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;
}