欢迎光临
我们一直在努力

打卡信奥刷题(3576)用C++实现信奥题 P11468 有向树

P11468 有向树

题目描述

给定一棵 nnn 个结点的树,将树上所有的无向边变成给定方向的有向边,求所有简单路径的长度之和。

有向图中 a1a_1a1​ 到 axa_xax​ 的简单路径是形如 a1→a2→a3→⋯→axa_1 \\rightarrow a_2 \\rightarrow a_3\\rightarrow \\cdots \\rightarrow a_xa1​→a2​→a3​→⋯→ax​ 的路径,其中 a1,a2,a3,⋯ ,axa_1,a_2,a_3,\\cdots,a_xa1​,a2​,a3​,⋯,ax​ 这 xxx 个顶点互不相同,其长度为简单路径上的有向边数量。

输入格式

第一行一个整数 nnn,表示树上一共有 nnn 个结点。

接下来 n−1n – 1n−1 行,每行两个整数 u,vu,vu,v,表示一条有向边 u→vu\\rightarrow vu→v。

输出格式

一个整数,表示有向树上所有简单路径的长度之和。

输入输出样例 #1

输入 #1

5
1 2
1 3
1 4
1 5

输出 #1

4

输入输出样例 #2

输入 #2

5
1 2
3 1
4 1
5 1

输出 #2

10

输入输出样例 #3

输入 #3

4
1 2
2 3
3 4

输出 #3

10

输入输出样例 #4

输入 #4

6
1 2
3 2
4 3
5 3
6 3

输出 #4

11

说明/提示

1≤n≤2×1051 \\le n \\le 2\\times 10^51≤n≤2×105,1≤u,v≤n1\\le u, v \\le n1≤u,v≤n,保证输入数据的有向边在看作无向边时,图构成一棵树。

C++实现

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 2e5 + 10;
vector<int> g[N]; //邻接表
int cnt[N]; //每个点先前经过的点数
long long d[N]; //各点出发的路径长度
int in[N]; //入度
queue<int> q;

int main(){
int n;
cin >> n;
for (int i = 1 ; i < n ; i++){
int u,v;
scanf("%d %d",&u,&v);
g[v].push_back(u); //反向建图
in[u]++;
}
for (int i = 1 ; i <= n ; i++){
if (!in[i]) q.push(i);
}
long long sum = 0;
while (!q.empty()){
int pos = q.front();
q.pop();
for (int i = 0 ; i < g[pos].size() ; i++){
int to = g[pos][i];
cnt[to] += 1 + cnt[pos];
d[to] += d[pos] + cnt[pos] + 1;

in[to]—;
if (!in[to]) q.push(to);
}

sum += d[pos];
}
cout << sum << endl;
return 0;
}

在这里插入图片描述

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现,记录日常的编程生活、比赛心得,感兴趣的请关注,我后续将继续分享相关内容

赞(0)
未经允许不得转载:171主机测评 » 打卡信奥刷题(3576)用C++实现信奥题 P11468 有向树
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址