P11468 有向树

有向树

题目描述

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

有向图中 $a_1$ 到 $a_x$ 的简单路径是形如 $a_1\to a_2\to a_3\to \cdots \to a_x$ 的路径，其中 $a_1,a_2,a_3,\cdots ,a_x$ 这 $x$ 个顶点互不相同，其长度为简单路径上的有向边数量。

输入格式

第一行一个整数 $n$，表示树上一共有 $n$ 个结点。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条有向边 $u\to 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\le n\le 2\times 10^5$，$1\le u,v\le n$，保证输入数据的有向边在看作无向边时，图构成一棵树。

思路：

非常简单的题：拓扑排序+树上dp
反向存边然后拓扑排序过程中dp转移即可
g(u)表示以u点为起点可以到达的点的数量（不包括u本身）
f(u)表示以u点为起点的所有简单路径长度和
$u\to v$ 转移方程为：
$g(u)=g(v)+1$
$f(u)=f(v)+g(v)+1$

代码：

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
typedef long long ll;
#define FU(i, a, b) for(int i = (a); i <= (b); ++ i)
#define FD(i, a, b) for(int i = (a); i >= (b); -- i)
using namespace std;
const int N=200010;

vector<int> ljs(N);
vector<int> fj[N];
int f[N];
int g[N];

signed main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    int n;
    cin>>n;
    FU(i,1,n-1){
        int a,b;
        cin>>a>>b;
        ljs[a]++;
        fj[b].push_back(a);
    }
    queue<int> x;
    FU(i,1,n){
        if(ljs[i]==0){
            x.push(i);
        }
    }
    while(!x.empty()){
        int t = x.front();
        x.pop();
        for(int e: fj[t]){
            ljs[e]--;
            if(ljs[e]==0){
                x.push(e);
            }
            g[e]+=g[t]+1;
            f[e]+=f[t]+g[t]+1;
        }
    }
    int ans = 0 ;
    FU(i,1,n){
        ans+=f[i];
    }
    cout<<ans<<endl;
    return 0;
}