D
逆向思维，考虑一条边被多少条路径作为答案。
很套路吧，想到每次找到图中最大的边，断开，它的贡献为两边联通块的大小相乘再乘它的权值。反着来，每次用最小的边连接两个块，用并查集维护。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define uint unsigned int
#define LL long long
using namespace std;
const int MAXN = 1e5 + 5;
struct Node {
int X, Y, Z;
bool operator < (const Node P) const { return Z < P.Z; }
}arr[MAXN];
int n, fa[MAXN], siz[MAXN];
LL ans;
// 可把删边看成加边
int Find_Set(int x) { return fa[x] != x ? fa[x] = Find_Set(fa[x]) : fa[x]; }
void Union_Set(int x, int y, int z) {
int u = Find_Set(x), v = Find_Set(y);
ans += (LL)siz[u] * siz[v] * z;// printf("|%lld|", ans);
fa[u] = v; siz[v] += siz[u]; siz[u] = 0;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) fa[i] = i, siz[i] = 1;
for(int i = 1; i < n; i ++) scanf("%d%d%d", &arr[i].X, &arr[i].Y, &arr[i].Z);
sort(arr + 1, arr + n);
for(int i = 1; i < n; i ++) Union_Set(arr[i].X, arr[i].Y, arr[i].Z);
printf("%lld", ans);
return 0;
}
E
对于循环什么的如果发现 for 不好写就写 while
贪心，很常见的贪心。
两种方法：
1.考虑按左端点排序，维护一个 \(L\) 表示现在选到第几个位置了，若线段 \([l,r]\) 满足 \(l\leq L\)，则将 \(r\) 加入优先队列里，每次优先选 \(r\) 小的。
2.按左端点为第一关键字，右端点为第二关键字排序。每次优先取左端点。
Code way 1
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#define uint unsigned int
#define LL long long
using namespace std;
const int MAXN = 2e5 + 5;
struct Node {
int X, Y;
bool operator < (const Node P) const { return P.X == X ? Y < P.Y : X < P.X; }
}arr[MAXN];
int T, n, L;
priority_queue <int, vector <int>, greater <int> > que;
int main() {
scanf("%d", &T);
while(T --) {
bool f = 1;
scanf("%d", &n);
while(!que.empty()) que.pop();
for(int i = 1; i <= n; i ++) scanf("%d%d", &arr[i].X, &arr[i].Y);
sort(arr + 1, arr + 1 + n); L = 0;
int g = 1;
while(que.size() || g <= n) {
while(arr[g].X <= L && g <= n) que.push(arr[g].Y), g ++;
if(que.empty()) { L = arr[g].X + 1; g ++; continue; }
int t = que.top(); que.pop();
if(L > t) { f = 0; break; }
L ++;
}
if(f) printf("Yes\n");
else printf("No\n");
}
return 0;
}
未完待续。（