P11468 有向树

reductt · 2024-12-27 20:08:45 · 题解

笑点解析：感觉这个题是最签到的题。

我们考虑求出以每一个点开头的简单路径长度和，然后加起来就是答案了。

首先这个有向树一定是一个有向无环图，因为树上一定没有环，所以就可以做拓扑。

设 f_u 为以点 u 开头的简单路径长度和，g_u 为 u 可以到达的点的数量（不包括 u 自己本身）。

然后画个图就可以得到转移方程：

关于 f_u 的转移里为什么是 g_v + f_v + 1 的原因：u 通过点 v 的所有简单路径的长度都比 v 的简单路径长度大 1，也就是 f_v + 1 \times g_u ，再加上 u \rightarrow v 这条路径，就是 g_v + f_v + 1，很好理解。

然后答案就是 \sum_{i=1}^{n} f_i。写个拓扑排序建个反图算一下就行了，时间复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i = (a); i <= (b); ++ i)
#define pb push_back

const int N = 2e5 + 10;
int n, outd[N], g[N], f[N];
vector<int> G[N];
queue<int> que;

signed main() {
    scanf("%lld", &n);
    FOR(i, 1, n - 1) {
        int u, v;
        scanf("%lld%lld", &u, &v);
        G[v].pb(u), outd[u] ++;
    }

    FOR(i, 1, n) if(!outd[i]) que.push(i);
    while(que.size()) {
        int u = que.front(); que.pop();
        for(int v: G[u]) {
            g[v] += g[u] + 1;
            f[v] += f[u] + g[u] + 1;
            if(!(-- outd[v])) que.push(v);
        }
    }

    int ans = 0;
    FOR(i, 1, n) ans += f[i];
    printf("%lld\n", ans);

    return 0;
}