潍坊定制网站搭建,开发网站和电脑软件的区别,会员管理系统哪个好用,如何制定网站建设规划正题
题目链接:https://www.luogu.org/problemnew/show/P5007 题目大意
一棵树每个点有点权(若T0T0T0点权为1#xff0c;若T1T1T1点权为该点的编号)。求所有不包含祖先关系的集合的点权之和的和。 解题思路
设fif_ifi表示iii的子树的集合点权之和#xff0c;gig_igi表…正题
题目链接:https://www.luogu.org/problemnew/show/P5007 题目大意
一棵树每个点有点权(若T0T0T0点权为1若T1T1T1点权为该点的编号)。求所有不包含祖先关系的集合的点权之和的和。 解题思路
设fif_ifi表示iii的子树的集合点权之和gig_igi表示iii的子树的集合个数。 然后有 fxfx∗gyfy∗gxfxfyf_xf_x*g_yf_y*g_xf_xf_yfxfx∗gyfy∗gxfxfy gxgx∗gygxgyg_xg_x*g_yg_xg_ygxgx∗gygxgy xxx是yyy的父节点
然后我们要计算入xxx这个点让fxfxwxf_xf_xw_xfxfxwxgxgx1g_xg_x1gxgx1 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1001000,XJQ1e87;
ll n,T,tot,g[N],f[N],ls[N];
struct node{ll to,next;
}a[N*2];
void addl(ll x,ll y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs(ll x,ll fa)
{for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa) continue;dfs(y,x);f[x](f[x]*g[y]f[y]*g[x]f[x]f[y])%XJQ;g[x](g[x]*g[y]g[x]g[y])%XJQ;}f[x](f[x]1T*(x-1))%XJQ;g[x];
}
int main()
{scanf(%lld%lld,n,T);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}dfs(1,0);printf(%lld,f[1]);
}
