原题传送门 这个题目就比较套路了 此前做过三个比较相似的题目
就是并查集的同时维护一些信息，这题只要维护结点个数 按照边从小到大连 对于目前一条 ( x , y , l ) (x,y,l) (x,y,l)，找到 x x x的祖先 s 1 s1 s1， y y y的祖先 s 2 s2 s2， a n s l + = s i z e s 1 ∗ s i z e s 2 ans_{l}+=size_{s1}*size_{s2} ansl+=sizes1∗sizes2
Code：
#include <bits/stdc++.h> #define maxn 200010 #define LL long long using namespace std; struct Line{ int x, y, len; }line[maxn]; int n, m, f[maxn], g[maxn]; LL ans[maxn]; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } bool cmp(Line x, Line y){ return x.len < y.len; } int getfa(int k){ return f[k] == k ? k : f[k] = getfa(f[k]); } int main(){ n = read(), m = read(); for (int i = 1; i < n; ++i) line[i].x = read(), line[i].y = read(), line[i].len = read(); sort(line + 1, line + n, cmp); for (int i = 1; i <= n; ++i) f[i] = i, g[i] = 1; for (int i = 1; i < n; ++i){ int x = line[i].x, y = line[i].y; int s1 = getfa(x), s2 = getfa(y); ans[line[i].len] += 1LL * g[s1] * g[s2]; f[s1] = s2, g[s2] += g[s1]; } for (int i = 1; i < maxn; ++i) ans[i] += ans[i - 1]; while (m--) printf("%lld ", ans[read()]); return 0; }