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考级编程题实现、白名单赛事考题实现,记录日常的编程生活、比赛心得,感兴趣的请关注,我后续将继续分享相关内容




![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)

