P9161 Trees题目背景ZHY 有很多树每个树上都有很多点每个点上都有一个数但他忘记了每个点上写的数是什么了。题目描述ZHY 拥有mmm棵树每棵树形态相同且均有nnn个点。定义(i,j)(i,j)(i,j)是第iii棵树上的第jjj个点你需要为每个点(i,j)(i,j)(i,j)赋一个值a(i,j)a_{(i,j)}a(i,j)​且满足以下条件对于∀i∈[1,m],∀j∈[1,n]\forall i \in [1,m],\forall j \in [1,n]∀i∈[1,m],∀j∈[1,n]有a(i,j)∈{0,1}a_{(i,j)}\in\{0,1\}a(i,j)​∈{0,1}。对于∀i∈[1,n]\forall i \in [1,n]∀i∈[1,n]有∑j1ma(j,i)≤1\sum_{j1}^m a_{(j,i)}\le 1∑j1m​a(j,i)​≤1。对于任意的一条边(u,v)(u,v)(u,v)和i∈[1,m]i \in [1,m]i∈[1,m]有a(i,u)a(i,v)≤1a_{(i,u)}a_{(i,v)}\le 1a(i,u)​a(i,v)​≤1。请你计算有多少种赋值方式对109710^971097取模。注意这mmm棵树是有序的。输入格式第一行两个正整数n,mn,mn,m。接下来n−1n-1n−1行每行两个正整数u,vu,vu,v表示这mmm棵树中每棵树都有一条从uuu到vvv的无向边。保证数据可以构成一棵树。输出格式输出一行表示答案。输入输出样例 #1输入 #13 1 1 2 2 3输出 #15输入输出样例 #2输入 #25 2 1 2 1 3 2 4 2 5输出 #2103说明/提示本题使用捆绑数据。对于所有的数据1≤n≤1061 \le n \le 10^61≤n≤1061≤m≤1091 \le m \le 10^91≤m≤109。Subtask 010 ptsn,m≤4n,m \le 4n,m≤4。Subtask 130 ptsn,m≤103n,m \le 10^3n,m≤103。Subtask 215 ptsn≤103n \le 10^3n≤103。Subtask 325 ptsm1m1m1。Subtask 420 pts无特殊限制。C实现#includebits/stdc.h#definemod1000000007//模数usingnamespacestd;constintN1e610;intn,m;longlongdp[N][2];vectorintvec[N];voiddfs(intcur,intfa){//因为是无向边需要记录它的父亲以避免重复for(inti0;ivec[cur].size();i){inttovec[cur][i];if(tofa)//判断父亲continue;dfs(to,cur);//先搜索再转移不然dp[to][0/1]还没有算出来转移无效dp[cur][0](dp[cur][0]*(dp[to][0]m*dp[to][1]%mod))%mod;dp[cur][1](dp[cur][1]*(dp[to][0](m-1)*dp[to][1]%mod))%mod;//状态转移}}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnm;for(inti1;in;i){intu,v;cinuv;vec[u].push_back(v);vec[v].push_back(u);//记得存双向边}for(inti1;in;i)dp[i][0]dp[i][1]1;//初始状态dfs(1,0);//从根结点深搜cout(dp[1][0]m*dp[1][1]%mod)%mod;//答案return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容