百度站长平台网站提交,网站制作的核心技术,网站开发怎么使用sharepoint,深圳建网站哪个好正题
题目大意:https://www.luogu.org/problem/P2796 题目大意
求一棵树中有多少个子树。 解题思路
考虑dpdpdp。 fif_ifi表示已iii这个点为根的子树个数。 动态转移方程fx∏x−y(fy1)f_x\prod_{x-y}(f_y1)fxx−y∏(fy1)
答案就是∑i1nfi\sum_{i1}^nf_…正题
题目大意:https://www.luogu.org/problem/P2796 题目大意
求一棵树中有多少个子树。 解题思路
考虑dpdpdp。 fif_ifi表示已iii这个点为根的子树个数。 动态转移方程fx∏x−y(fy1)f_x\prod_{x-y}(f_y1)fxx−y∏(fy1)
答案就是∑i1nfi\sum_{i1}^nf_ii1∑nfi codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N110000,XJQ1e97;
struct node{ll to,next;
}a[N*2];
ll n,ls[N],f[N],tot,ans;
void addl(ll x,ll y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dp(ll x,ll fa)
{f[x]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa) continue;dp(y,x);f[x]f[x]*(f[y]1)%XJQ;}
}
int main()
{scanf(%lld,n);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}dp(1,0);for(ll i1;in;i)(ansf[i])%XJQ;printf(%lld,ans);
}
