GYM103660E. Disjoint path on tree count

GYM103660E.Disjoint Path On Tree

Topic ideas

Given a tree , Find the logarithm of disjoint paths on the tree .

Excuse me ： Disjoint path logarithm = Total path logarithm - Intersection path logarithm

Consider how to calculate the logarithm of intersecting paths ： Enumeration points $i$ As a path $LCA$, Then the number of intersection schemes at this time is $i$ And $LCA$ be not in $i$ The number of paths × $LCA $by$i $The\; number\; of\; paths+$LCA$All\; in$i$ Path logarithm of .

Then count directly on the tree and then exclude .

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;
}