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
 
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 ;
}

最新文章

  1. codeforces C. Bits(数学题+或运算)
  2. Web 应用程序项目 MvcApplication1 已配置为使用 IIS。
  3. Swift下标
  4. 解析php中die(),exit(),return的区别
  5. SNMP协议具体解释
  6. robotframework自动化系列:修改流程
  7. iBatis &amp; myBatis &amp; Hibernate 要点记录
  8. rhel7 启动网络
  9. Vjudge Code
  10. C++: 模板函数定义与声明分离;
  11. python 常忘代码查询 和autohotkey补括号脚本和一些笔记和面试常见问题
  12. excel表格导入数据库数据存在则更新不存在添加
  13. Ubuntu18.04下可以完美运行Quake3 Arena
  14. ES5-ES6-ES7_let关键字声明变量
  15. c++ 接口类
  16. 26.pymysql、pymongo、redis-py安装
  17. toast js
  18. c# 为什么要使用Array、ArrayList、List?
  19. 如何在 ASP.NET 中(服务器端)主动清除(HTTP内容响应时)浏览器中的 Cookies 数据
  20. 网站用sqlite库,报attempt to write a readonly database,解决方法

热门文章

  1. git pull和git merge区别&amp;&amp;Git冲突:commit your changes or stash them before you can merge. 解决办法
  2. python 中元祖tuple的使用
  3. POJ - 1511 - 两次SPFA
  4. org.springframework.beans.factory.CannotLoadBeanClassException: Cannot find class [com.my.service.ProductService] for bean with name &#39;productService&#39; defi报错解决方法
  5. spark程序设计
  6. shell 脚本中双引号 单引号 反引号 的区别
  7. 20145316《Java程序设计》第六周学习总结
  8. [2012-12-18 14:59:31]AS3 常用正则表达式的总结-不用google了,我帮收集的很多了
  9. 联想笔记本电脑的F1至F12键盘问题。怎么设置才能不按FN就使用F1
  10. CSS Pseudo-classes(伪类)