HDU-4705-树形dp/组合数学
2024-08-27 22:25:18
Y
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2762 Accepted Submission(s): 800
Problem Description
Sample Input
4
1 2
1 3
1 4
1 2
1 3
1 4
Sample Output
1
Hint
1. The only set is {2,3,4}.
2. Please use #pragma comment(linker, "/STACK:16777216")
Source
可以先找到三个点的SIMPLE-PATH的数量,然后让C(N,3)-SIMPLE-PATH就是答案了。
对于节点u,子树的节点个数为n1,n2,,,,,nk的话,以u为中点的SIMPLE-PATH的数量就是n1(n2+n3+...+nk)+n2(n3+...+nk)+.....+nk-1*nk,这一步可以在遍历儿子时迭代实现。
别忘记还有一颗子树是父亲节点,N-sum[u].
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
#define LL long long
vector<int>g[];
LL sum[];
LL tot,N;
void dfs(int u,int pre){
sum[u]=;
LL res=;
for(int i=;i<g[u].size();++i){
if(g[u][i]==pre) continue;
dfs(g[u][i],u);
sum[u]+=sum[g[u][i]];
tot+=res*sum[g[u][i]];
res+=sum[g[u][i]];
}
tot+=res*(N-sum[u]);
}
int main()
{
while(cin>>N){int u,v;
tot=;
for(int i=;i<N;++i){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(,);
LL tt=;
LL ans=N*(N-)*(N-)/;
cout<<ans-tot<<endl;
for(int i=;i<=N;++i) g[i].clear();
}
return ;
}
最新文章
- codeforces C. Bits(数学题+或运算)
- Web 应用程序项目 MvcApplication1 已配置为使用 IIS。
- Swift下标
- 解析php中die(),exit(),return的区别
- SNMP协议具体解释
- robotframework自动化系列:修改流程
- iBatis &; myBatis &; Hibernate 要点记录
- rhel7 启动网络
- Vjudge Code
- C++: 模板函数定义与声明分离;
- python 常忘代码查询 和autohotkey补括号脚本和一些笔记和面试常见问题
- excel表格导入数据库数据存在则更新不存在添加
- Ubuntu18.04下可以完美运行Quake3 Arena
- ES5-ES6-ES7_let关键字声明变量
- c++ 接口类
- 26.pymysql、pymongo、redis-py安装
- toast js
- c# 为什么要使用Array、ArrayList、List?
- 如何在 ASP.NET 中(服务器端)主动清除(HTTP内容响应时)浏览器中的 Cookies 数据
- 网站用sqlite库,报attempt to write a readonly database,解决方法
热门文章
- git pull和git merge区别&;&;Git冲突:commit your changes or stash them before you can merge. 解决办法
- python 中元祖tuple的使用
- POJ - 1511 - 两次SPFA
- org.springframework.beans.factory.CannotLoadBeanClassException: Cannot find class [com.my.service.ProductService] for bean with name &#39;productService&#39; defi报错解决方法
- spark程序设计
- shell 脚本中双引号 单引号 反引号 的区别
- 20145316《Java程序设计》第六周学习总结
- [2012-12-18 14:59:31]AS3 常用正则表达式的总结-不用google了,我帮收集的很多了
- 联想笔记本电脑的F1至F12键盘问题。怎么设置才能不按FN就使用F1
- CSS Pseudo-classes(伪类)