GYM103660E.Disjoint Path On Tree 树上计数

GYM103660E.Disjoint Path On Tree 题目思路

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

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

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

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

Code

#include 
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
vector 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  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