为啥 23 分,不懂(虽然我过了)
查看原帖
为啥 23 分,不懂(虽然我过了)
1001535
封禁用户楼主2024/8/5 20:03
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e7 + 5;
const int MAXX = 500000004;
vector <int> adj[MAXN];
bool vis[MAXN];
int n;
int sum;
int u, v;
int dfs(int x) {
	int children_size = 0;
	int t;
	for (auto step : adj[x]) {
		if (vis[step] == 0) {
			vis[step] = 1;
			t = dfs(step);
			vis[step] = 0;
			children_size += t;
			int temp = t;
			sum +=(((temp) * (n - temp) % MOD) * (n - temp - 1) % MOD + ((temp - 1) * (temp) % MOD) * (n - temp) % MOD) % MOD;
		}
	}
	return children_size + 1;
}
//void dfs(int node, int parent, int root) {
//    for (int child : adj[node]) {
//        if (child != parent) {
//            dist[root][child] = dist[root][node] + 1;
//            dfs(child, node, root);
//        }
//    }
//}
signed main() {
	cin >> n;
	for (int i = 1 ; i < n; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vis[1] = 1;
	dfs(1);
	cout << (sum / 2  % MOD) % MOD;
//    cout << 1;
	return 0;
}
2024/8/5 20:03
加载中...