比赛时候写复杂了……

我写的是 计算每个节点树内所有点到某个点的距离和。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + ;
vector<int> g[maxn];
int son[maxn];
ll d[maxn]; ///树内所有点到某个点的距离和
int odd[maxn];
int even[maxn];
void dfs1(int u, int fa)
{
d[u] = ;
son[u] = ;
son[u]++;
even[u] = ;
for(int i = ; i < (int)g[u].size(); i++)
{
int v = g[u][i];
if(v == fa) continue;
dfs1(v, u);
son[u] += son[v];
even[u] += odd[v];
d[u] += d[v] + son[v];
}
odd[u] = son[u] - even[u];
// printf("%d %I64d\n", u, d[u]);
}
ll ans = ;
void dfs2(int u, int fa)
{
for(int i = ; i < (int)g[u].size(); i++)
{
int v = g[u][i];
if(v == fa) continue;
d[v] = d[v] + (d[u] - d[v] - (ll)son[v]) + (ll)(son[u] - son[v]);
odd[v] += (son[u] - son[v] - odd[u] + even[v]);
son[v] = son[u];
ans += ((d[v] + odd[v]) / 2LL);
dfs2(v, u);
}
}
int main()
{
int n; scanf("%d", &n);
for(int i = ; i <= n - ; i++)
{
int u, v; scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(, );
dfs2(, );
ans += (d[] + odd[]) / 2LL;
printf("%lld\n", ans / 2LL);
return ;
}

Code

实际上这题只需要计算树上任意两点的距离和,枚举每条边的贡献就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + ;
vector<int> g[maxn];
int n;
ll ans, odd, even;
int dfs(int u, int fa, int dep)
{
if(dep % ) odd++;
else even++;
int son = ; ///统计子树大小
for(int i = ; i < (int)g[u].size(); i++)
{
int v = g[u][i];
if(v == fa) continue;
int sing = dfs(v, u, dep + );
ans += (ll)sing * (n - sing); ///枚举每条边的贡献
son += sing;
}
return son;
}
int main()
{
scanf("%d", &n);
for(int i = ; i <= n - ; i++)
{
int u, v; scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(, , );
ans = (ans + (ll)odd * even) / ;
printf("%lld\n", ans);
return ;
}

Code

最新文章

  1. tyvj1463 智商问题
  2. 使用C++11的一点总结
  3. linux 内核学习之八 进程调度过程分析
  4. (笔记)Linux内核学习(九)之内核内存管理方式
  5. CardsTube/YouTubePlaylist
  6. myEclipse和eclipse修改或复制项目名称后-更新部署名称
  7. Div里面载入另一个页面的实现(取代框架)(AJax)
  8. Liunx的DHCP配置
  9. Spring boot 默认静态资源路径与手动配置访问路径
  10. 解决html5 canvas 绘制字体、图片与图形模糊问题
  11. Java DualPivotQuickSort 双轴快速排序 源码 笔记
  12. JavaScript实现预览本地上传图片
  13. 8. 同步锁Lock
  14. JS--bom对象:borswer object model浏览器对象模型
  15. {python之协程}一 引子 二 协程介绍 三 Greenlet 四 Gevent介绍 五 Gevent之同步与异步 六 Gevent之应用举例一 七 Gevent之应用举例二
  16. 9、后记:公司管理经验总结 - CEO之公司管理经验谈
  17. maven+spring+junit测试要注意的事情
  18. Security Software Engineer
  19. 详解MathType中如何插入特殊符号
  20. Hive的基本介绍

热门文章

  1. Python基础——类
  2. Tomcat上传文件报错:returned a response status of 403 Forbidden
  3. drf版本控制 django缓存
  4. poj 2718 切数问题 穷竭搜索
  5. Vmware安装与使用
  6. JAVA中变量的类型及命名规范
  7. 【MySQL】MySQL备份和恢复
  8. 20,序列化模块 json,pickle,shelve
  9. Asp.net HttpWebRequest和HttpWebResponse发送和接受任何类型数据
  10. Multi-Dimensional Recurrent Neural Networks