admin 管理员组

文章数量: 887021

蘑菇

蘑菇
仔 细 思 考 ， 发 现 一 个 d p 就 做 完 了 （ 显 然 我 没 想 出 来 ） 仔细思考，发现一个dp就做完了（显然我没想出来） 仔细思考，发现一个dp就做完了（显然我没想出来）
好 好 想 一 下 ， 树 的 操 作 好 像 就 那 么 几 种 ， 想 这 种 求 和 的 怎 么 看 都 像 树 形 d p ， 所 以 我 们 就 做 完 了 好好想一下，树的操作好像就那么几种，想这种求和的怎么看都像树形dp，所以我们就做完了 好好想一下，树的操作好像就那么几种，想这种求和的怎么看都像树形dp，所以我们就做完了

f[x][0]表示不包括x联通块的乘积，f[x][1]表示包括x连通块的乘积，随便搞一搞就做完了

#include<bits/stdc++.h>
using namespace std;typedef unsigned long long ll;
ll mod=998244353;
const int N=1e6+5;
int n;
long long dp[N][2];
int cnt=0,head[N];
struct edge{int link,v;
}q[N<<1];
void put(int u,int v){q[++cnt].v=v;q[cnt].link=head[u];head[u]=cnt;
}
void dfs(int s,int fa){dp[s][0]=1,dp[s][1]=1;for(int i=head[s];i;i=q[i].link){int v=q[i].v;if(v==fa) continue;dfs(v,s);ll tp1=dp[s][1],tp0=dp[s][0];dp[s][1]=((1ull*dp[v][1]*tp1%mod+1ull*dp[v][0]*tp1%mod)%mod+1ull*dp[v][1]*tp0%mod)%mod;dp[s][0]=((1ull*dp[v][0]*tp0%mod+1ull*dp[v][1]*tp0%mod))%mod;}
}
ll ksm(ll x,ll pow){ll ans=1,res=x;while(pow){if(pow&1) ans=1ull*ans*res%mod;res=1ull*res*res%mod;pow>>=1;}return ans;
}
ll ny(ll x){return ksm(x,mod-2);
}
int main(){scanf("%d",&n);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);put(u,v),put(v,u);}dfs(1,0);ll anss=ksm(2,n-1);ll ans2=ny(anss);printf("%lld",(1ull*dp[1][1]*ans2%mod));
}

本文标签： 蘑菇

版权声明：本文标题：蘑菇 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687562652h116156.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。