博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【HDU 5647】DZY Loves Connecting(树DP)
阅读量:5870 次
发布时间:2019-06-19

本文共 2944 字,大约阅读时间需要 9 分钟。

DZY Loves Connecting

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 332    Accepted Submission(s): 112
Problem Description
DZY has an unrooted tree consisting of
n nodes labeled from
1 to
n.
DZY likes connected sets on the tree. A connected set
S is a set of nodes, such that every two nodes
u,v in
S can be connected by a path on the tree, and the path should only contain nodes from
S. Obviously, a set consisting of a single node is also considered a connected set.
The size of a connected set is defined by the number of nodes which it contains. DZY wants to know the sum of the sizes of all the connected sets. Can you help him count it?
The answer may be large. Please output modulo
109+7.
 
Input
First line contains
t denoting the number of testcases.
t testcases follow. In each testcase, first line contains
n. In lines
2n,
ith line contains
pi, meaning there is an edge between node
i and node
pi. (
1pii1,2in)
(
n1。 sum of
n in all testcases does not exceed
200000)
 
Output
Output one line for each testcase, modulo
109+7.
 
Sample Input
 
2 1 5 1 2 2 3
 
Sample Output
 
1 42
Hint
In the second sample, the 4 edges are (1,2),(2,3),(2,4),(3,5). All the connected sets are {1},{2},{3},{4},{5},{1,2},{2,3},{2,4},{3,5},{1,2,3},{1,2,4},{2,3,4},{2,3,5},{1,2,3,4},{1,2,3,5},{2,3,4,5},{1,2,3,4,5}. If you need a larger stack size, please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.
 
Source
 

一个挺直接的树DP。之前TC的一个原题,。比赛时死活没啃出来。。

。太嫩了……

题目大意:给出一个树,详细建法就不细说了。每一个点贡献为1,问树上全部不同集合的合计贡献。

首先对于每一个点,我们能够求出它所在的集合数量。

开个数组cnt。表示第i个点在其子树中所在的集合数。这样cnt[i]就等于i全部孩子的cnt+1的乘积。事实上这里用到了组合,从全部孩子中能够随意选择一定的集合(+1表示空集)进行组合。

求出集合数是为了求贡献,遍历到i的某个孩子的时候,新添加的贡献事实上就是之前的全部贡献乘上该孩子的集合数+1(选择某些集合组合),然后对于之前遍历的子数。该孩子也能够提供贡献,也就是该孩子的贡献乘上当前出现的集合数。

口述表达的不好,也不会做那种图。

。还是看代码吧,就俩公式。。

代码例如以下:

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long#define Pr pair
#define fread() freopen("in.in","r",stdin)#define fwrite() freopen("out.out","w",stdout)using namespace std;const int INF = 0x3f3f3f3f;const int msz = 10000;const int mod = 1e9+7;const double eps = 1e-8;struct Edge{ int v,next;};Edge eg[233333];int head[233333];//0存当前节点往下包括当前节点的区间数 1存当前节点的子树中全部包括当前节点的贡献LL dp[233333][2];LL ans;void dfs(int u){ dp[u][1] = 1; dp[u][0] = 1; for(int i = head[u]; i != -1; i = eg[i].next) { dfs(eg[i].v); //当前点子树中包括当前点的区间的贡献 dp[u][1] = (dp[u][1]*(dp[eg[i].v][0]+1)+dp[eg[i].v][1]*dp[u][0])%mod; dp[u][0] = (dp[u][0]*(dp[eg[i].v][0]+1))%mod; } ans = (ans+dp[u][1])%mod;}int main(){ //fread(); //fwrite(); int x,t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(head,-1,sizeof(head)); for(int i = 2; i <= n; ++i) { scanf("%d",&x); eg[i].v = i; eg[i].next = head[x]; head[x] = i; } ans = 0; dfs(1); printf("%lld\n",ans); } return 0;}

转载地址:http://ybxnx.baihongyu.com/

你可能感兴趣的文章
[20170302]正常关闭数据库日志丢失3.txt
查看>>
ArcGIS JS 学习笔记2 实现仿百度的拖拽画圆
查看>>
8Manage SPM:随时随地掌控采购管理
查看>>
tomcat会话之持久化会话管理器
查看>>
从一道算法题说去2
查看>>
SharePoint 2013 在母版页中插入WebPart
查看>>
SharePoint 2016 入门视频教程
查看>>
Spring Boot(一)启动方式
查看>>
oracle 数据库单实例和rac中listener的区别
查看>>
没有身份凭证的情况下,攻击者就能登录FreeRADIUS
查看>>
数据库拆分的几种方式
查看>>
app软件开发功能流程
查看>>
CNN实现“读脑术”,成功解码人脑视觉活动,准确率超50%
查看>>
红豆集团推出首家无人服装零售店,跟无人便利店有何不同?
查看>>
CSS3新样式
查看>>
Docker 安装 MySQL
查看>>
设计模式:单例模式(Singleton)
查看>>
利用EntLib授权机制实现对ASP.NET页面的自动授权
查看>>
《WCF后续之旅》博文系列总结[共17篇]
查看>>
NTOPNG修改密码
查看>>