E. Sergey and Subway
2024-08-30 05:58:54
比赛时候写复杂了……
我写的是 计算每个节点树内所有点到某个点的距离和。
#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
最新文章
- tyvj1463 智商问题
- 使用C++11的一点总结
- linux 内核学习之八 进程调度过程分析
- (笔记)Linux内核学习(九)之内核内存管理方式
- CardsTube/YouTubePlaylist
- myEclipse和eclipse修改或复制项目名称后-更新部署名称
- Div里面载入另一个页面的实现(取代框架)(AJax)
- Liunx的DHCP配置
- Spring boot 默认静态资源路径与手动配置访问路径
- 解决html5 canvas 绘制字体、图片与图形模糊问题
- Java DualPivotQuickSort 双轴快速排序 源码 笔记
- JavaScript实现预览本地上传图片
- 8. 同步锁Lock
- JS--bom对象:borswer object model浏览器对象模型
- {python之协程}一 引子 二 协程介绍 三 Greenlet 四 Gevent介绍 五 Gevent之同步与异步 六 Gevent之应用举例一 七 Gevent之应用举例二
- 9、后记:公司管理经验总结 - CEO之公司管理经验谈
- maven+spring+junit测试要注意的事情
- Security Software Engineer
- 详解MathType中如何插入特殊符号
- Hive的基本介绍