GYM103660E.Disjoint Path On Tree 树上计数

GYM103660E.Disjoint Path On Tree

题目思路

给定一棵树，求树上不相交的路径对数。

容斥一下：不相交路径对数 = 总路径对数 - 相交路径对数

考虑如何计算相交路径对数：枚举点$i$作为一条路径的$LCA$，则此时的相交方案数为经过$i$且$LCA$不在$i$的路径数 × $LCA $为$i $的路径数+$LCA$都在$i$的路径对数。

那么直接树上计数然后容斥即可。

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
vector<signed> g[N];

int sz[N], ans = 0;
int n = 0;

void dfs(int u, int fa){
    
    int res = 0;
    sz[u] = 0;
    for(auto v : g[u]){
    
        if(v == fa) continue;
        dfs(v, u);
        (res += sz[v] * sz[u]) %= MOD;
        sz[u] += sz[v];
    }
    sz[u]++;
    int t = (res + sz[u]) % MOD;
    (ans += ((n - sz[u]) * sz[u] % MOD * t % MOD)) %= MOD;
    (ans += (t * (t + 1) / 2) % MOD) %= MOD;
}

inline void solve(){
    
    cin >> n; ans = 0;
    for(int i = 1; i <= n; i++) g[i].clear();
    for(int i = 1; i <= n - 1; i++){
    
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(1, 0);
    int path = ((n * (n + 1)) / 2) % MOD, all = ((path * (path + 1)) / 2) % MOD;
    ans = ((all - ans) % MOD + MOD) % MOD;
    cout << ans << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}